\(M\)-alternating paths in \(n\)-extendable bipartite graphs (Q1402062): Difference between revisions

Let \(n\) be a positive integer and \(G\) be a graph with \(v\) vertices, \(v\geq 2n+2\). \(G\) is said to be \(n\)-extendable if \(G\) has \(n\) independent edges and any \(n\) independent edges of \(G\) are contained in a perfect matching of \(G\). Let \(G\) be a bipartite graph with bipartition \((X,Y)\) which has a perfect matching. It is proved that \(G\) is \(n\)-extendable if and only if for any perfect matching \(M\) of \(G\) and for each pair of vertices \(x\) in \(X\) and \(y\) in \(Y\) there are \(n\) internally disjoint \(M\)-alternating paths connecting \(x\) and \(y\). Furthermore, these \(n\) paths start and end with edges in \(E(G)\backslash M\). This theorem is then generalized. Note that for a perfect matching \(M\) of \(G\) an \(M\)-alternating path \(P\) of \(G\) is a path in \(G\) where edges in \(M\) and edges in \(E(G)\backslash M\) appear on \(P\) alternately.