2-Factors in Graphs

Abstract

An account of $2$-factors in graphs and their history is presented. We give a direct graph-theoretic proof of the $2$-Factor Theorem and a new variant of it, and also a new complete characterisation of the maximal graphs without $2$-factors. This is based on the important works of Tibor Gallai on $1$-factors and of Hans-Boris Belck on $k$-factors, both published in 1950 and independently containing the theory of alternating chains. We also present an easy proof that a $(2k+1)$-regular graph with at most $2k$ leaves has a $2$-factor, and we describe all connected $(2k+1)$-regular graphs with exactly $2k+1$ leaves without a $2$-factor. This generalises Julius Petersen's famous theorem, that any $3$-regular graph with at most two leaves has a $1$-factor, and it generalises the extremal graphs Sylvester discovered for that theorem.