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.
