Almost all optimally coloured complete graphs contain a rainbow Hamilton path

Stephen Gould, Tom Kelly, Daniela Kuhn, Deryk Osthus

Research output: Contribution to journalArticlepeer-review

4 Downloads (Pure)


A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of Kn admits a rainbow path of length n-2. We show that almost all optimal edge-colourings of Kadmit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of Kand answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.
Original languageEnglish
Pages (from-to)57-100
Number of pages44
JournalJournal of Combinatorial Theory. Series B
Early online date3 May 2022
Publication statusPublished - Sept 2022

Bibliographical note

Funding Information:
This project has received partial funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 786198 , D. Kühn and D. Osthus). The research leading to these results was also partially supported by the EPSRC , grant nos. EP/N019504/1 (T. Kelly and D. Kühn) and EP/S00100X/1 (D. Osthus).

Publisher Copyright:
© 2022 The Author(s)


  • Andersen's conjecture
  • Edge-colouring
  • Rainbow path
  • Rainbow cycle
  • Hypergraph matchings
  • Distributive absorption
  • Latin squares


Dive into the research topics of 'Almost all optimally coloured complete graphs contain a rainbow Hamilton path'. Together they form a unique fingerprint.

Cite this