ETH Zürich



Cycle packing


Over 50 years ago, Erdős and Gallai conjectured that the edges of every graph on n vertices can be decomposed into O(n) cycles and edges. They observed that one can easily get an O(n log n) upper bound by repeatedly removing the edges of the longest cycle. We make the first progress on this problem, showing that O(n log log n) cycles and edges suffice. We also prove the Erdős–Gallai conjecture for random graphs showing that whp G(np) (for most values of p) can be decomposed into a union of n/4 + np/2 + o(n) cycles and edges, which is asymptotically tight.

This is joint work with Conlon and Fox, and also Korandi and Krivelevich.


The Catalan Mathematical Society invites participants to this first congress of a biannual series focusing on current research topics across several areas of Mathematics.

Plenary talks and thematic sessions have been selected by the Scientific Committee of the SCM. Special thanks are due to the organisers of the thematic sessions and to the local mathematical community as a whole for their support to this congress.


Societat Catalana de Matemàtiques
Institut d'Estudis Catalans
Carrer del Carme, 47
08001 Barcelona

Phone: +34 933 248 583

Download a poster (high res)

Download a poster (low res)