M-alternating paths in n-extendable bipartite graphs Original Research Article

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)⧹M. This theorem is then generalized.