## Decomposition into two k-factors

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