Eulerian graph and union of cycles

Task number: 4175

Prove that the edges of each Eulerian graph can be decomposed into a disjoint union of cycles.

Is the decomposition unique? If not, is the number of cycles in the decomposition given uniquely?

  • Solution

    By induction: Any Eulerian graph has a closed Eulerian trail. If we select the shortest part of the trail between two occurrences of the same vertex along \( C \), then the edges of \( C \) determine the cycle.

    The graph \( G-C \) is Eulerian, ie from the inductive assumption it is a disjoint union of cycles. By adding \( C \) to this union, we cover all edges of \( G \).

    Neither the decomposition nor the number of cycles is unique, e.g. \( K_5 \) can be decomposed into two five-cycles or into two triangles and a four-cycle.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Proving or derivation task
Cs translation
Send comment on task by email