Nash-Williams’ cycle-decomposition theorem

Research output: Contribution to journalJournal articleResearchpeer-review

1333 Downloads (Pure)


We give an elementary proof of the theorem of Nash-Williams that a graph has an edge-decomposition into cycles if and only if it does not contain an odd cut. We also prove that every bridgeless graph has a collection of cycles covering each edge at least once and at most 7 times. The two results are equivalent in the sense that each can be derived from the other.
Original languageEnglish
Number of pages11
Publication statusPublished - 2016


Dive into the research topics of 'Nash-Williams’ cycle-decomposition theorem'. Together they form a unique fingerprint.

Cite this