4
$\begingroup$

I need to prove that given a graph which is $2k$-regular, I can find a 2-factor. Meaning, There is a sub-graph of the above graph, which contains all vertices, and is 2-regular.

I must say I have no idea where to start with this. so help would be greatly appreciated :)

Thanks.

1 Answers 1

4

Each component of the graph contains an Eulerian cycle.

Now, split each vertex in two, and keep incident to one of them all the incoming edges of the Eulerian cycle and to the other all the outgoing ones.

This gives a bipartite graph that is $k$-regular.

This graph contains a 1-factor as a consequence of the marriage theorem.

Glue the split vertices together, and this 1-factor turns out to be a two-factor of the original graph.