Decomposition into two k-factors
Task number: 4177
Prove that if a \( 2k \)-regular graph has an even number of edges in each component, then it can be decomposed into two edge-disjoint \( k \)-factors.
(Definitions: \( k \)-regular graph has all vertices of degree \( k \); factor is a subgraph with the same set of vertices; \( k \)-factor is a \( k \)-regular factor).
We split each component \( C \) into two \( k \)-factors independently of the other components.
Each component \( C \) is a connected Eulerian graph, i.e. it has a closed Eulerian trail. This trail has an even number of edges. We follow the trail and alternately divide the edges into two groups – edges in odd positions in a move to one group, edges in even to another.
By visiting a vertex, both groups receive one edge; at the first vertex, the first edge is compensated by adding the last edge to the second group.
Edges incident with a vertex are partitioned into two sets of the same size. Thus within both factors each vertex is of degree \( k \).