Nash-Williams’ cycle-decomposition theorem

Research output: Contribution to journalJournal articleResearchpeer-review

592 Downloads (Pure)

Abstract

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
JournalCombinatorica
Number of pages11
ISSN0209-9683
DOIs
Publication statusPublished - 2016

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

Cite this