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.