Suppose the graph G is n-connected, regular of degree n, and has an even number of vertices. Prove that G has a one-factor.
Petersen's 2-factor theorem (Theorem 5.40 in the notes) proves that every regular graph G of even degree has a 2-factor by nding a 1-factor in a regular bipartite graph which is constructed from an Eulerian trail of G. However, the choice of Eulerian trail and 1-factor determines which 2-factor is obtained. Consider the following Eulerian trail C of K7 where V (K7) = {0; 1; 2; 3; 4; 5; 6}.
C : 0; 1; 2; 3; 4; 5; 6; 0; 2; 4; 6; 1; 3; 5; 0; 3; 6; 2; 5; 1; 4; 0:
(a) List a 2-factor of K7 of type [3; 4] that could arise from C via the proof technique of Petersen's theorem, and explain why it could arise.
(b) List a 2-factor of K7 that could not arise from C via the proof technique of Petersen's theorem, and explain why it could not arise.