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.