Extensions to 2-Factors in Bipartite Graphs
Abstract
A graph is $d$-bounded if its maximum degree is at most $d$. We apply the Ore-Ryser Theorem on $f$-factors in bipartite graphs to obtain conditions for the extension of a $2$-bounded subgraph to a $2$-factor in a bipartite graph. As consequences, we prove that every matching in the $5$-dimensional hypercube extends to a $2$-factor, and we obtain conditions for this property in general regular bipartite graphs. For example, to show that every matching in a regular $n$-vertex bipartite graph extends to a $2$-factor, it suffices to show that all matchings with fewer than $n/3$ edges extend to $2$-factors.