5.3.2. 2-factorable graphs
Fact. Let G be 2-factorable.
Then it is 2k-regular
for some .
Petersen showed that the above necessary condition is sufficient as well:
Theorem 5.7. (Petersen, 1891): A graph G is 2-factorable iff G is 2k-regular for some integer .
Proof.
We have already noted that if G is a 2-factorable graph, then G is regular of positive even degree.
Conversely, suppose that G is 2k-regular
for some integer .
W.l.o.g. we can suppose that G is connected. Hence G is eulerian and so contains an eulerian circuit C.
Let . We define a bipartite graph H
with partite sets
and
, where
.
The graph H is k-regular and so, by Theorem 8.22, is 1-factorable. Hence is a 1-factorization of H.
Corresponding to each 1-factor of H a permutation
on the set
, defined by
.
Let be expressed as a product of disjoint
permutation cycles.
-
There is no permutation cycle of length 1 in this product: if
were a permution cycle, then this would imply that
. However, this further implies that
and that
, which is impossible.
-
There is no permutation cycle of length 2 in this product. For if
were a permutation cycle, then this would imply that
and
. This would indicate that
and that
both immediately follows and precedes
on C, contradicting the fact that no edge is repeated on a circuit.
Thus, the length of every permutation cycle in is at least 3.
Each permutation cycle
in therefore
gives rise to a cycle in G, and the product of disjoint permutation
cycles in
produces
a collection of mutually disjoint cycles in G containing all vertices of G, that is, a 2-factor
in G.
Since the 1-factors in H are
mutually edge-disjoint, the resulting 2-factors
in G are mutually edge-disjoint.
Hence, G is 2-factorable.