Bipartite Colour Classes, and the Step an Odd Cycle Does Not Take

If every colour class of an edge-colouring is bipartite, the classes multiply together into a proper $2^n$-colouring of the whole graph. A complete graph on more than $2^n$ vertices therefore has a non-bipartite class, and hence a monochromatic odd cycle. We prove this for arbitrary $N$ and $n$ by an injectivity argument that requires no graph theory at all. The odd cycle so produced need not be a triangle, and the gap is visible at the first non-trivial case. The complete graph $K_5$ carries a $2$-colouring with no monochromatic triangle, both classes being $5$-cycles, while every $2$-colouring of $K_6$ has one. The shortest monochromatic odd cycle guaranteed in a $2$-colouring of $K_5$ therefore has length five, and $R(3,3) = 6$.