Multicoloured Hamilton Cycles

The edges of the complete graph Kₙ are coloured so that no colour appears more than cn times, where $c < 1/32$ is a constant. We show that if n is sufficiently large then there is a Hamiltonian cycle in which each edge is a different colour, thereby proving a 1986 conjecture of Hahn and Thomassen. We prove a similar result for the complete digraph with $c < 1/64$. We also show, by essentially the same technique, that if t≥ 3, c < (2t²(1+t))⁻¹, no colour appears more than cn times and $t|n$ then the vertices can be partitioned into $n/t$ $t-$sets K₁,K₂,…,Kn/t such that the colours of the $n(t-1)/2$ edges contained in the Kᵢ's are distinct. The proof technique follows the lines of Erdős and Spencer's modification of the Local Lemma.