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).

  • Solution

    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 \).

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email