Every graph which admits a cycle cover also admits a uniform cycle cover.

73 Views Asked by At

I would like to prove

Every graph which admits a cycle cover also admits a uniform cycle cover.

but I can't even start.

To be clear on the definitions. A cycle cover of a graph $G$ is a set of subgraphs of $G$ that are cycles and the union of whose edge sets equals the set of edges of $G$. A uniform cycle cover is a cycle cover such that every two edges of $G$ are in the same number of cycles.

One guess is that taking all possible cycle could gives one such uniform cycle cover (lcm iff there are more components), but I have only two few examples.

Source: Bondy2008, p. 58 and Exercise 3.5.7 (Similar formulation: every graph without cut edges has a uniform cycle covering)