# There must be a monochromatic odd cycle in $t$-coloring of $K_{2^t+1}$

Prove: if we $t$-color the edges of the complete graph on $2^t+1$ vertices, then there must be a monochromatic odd cycle.

This is supposed to be an easy exercise but I haven't made much progress. Here are my attempts.

I have tried the probabilistic method, but it doesn't seem feasible because the number of possible odd cycles is $\frac{1}{2}2^{2^t+1}-(2^t+1)=2^{2^t}-2^t-1$ which doesn't seem like a workable number. In addition the probability that a cycle is monochromatic depends on the length. So the chance of an odd cycle is something like

$${2^t+1\choose 3}\frac{1}{t^2}+{2^t+1\choose 5}\frac{1}{t^4}+\cdots+{2^t+1\choose 2^t+1}\frac{1}{t^{2^t}}$$

and I really don't see this method being very helpful.

The other route is induction: suppose it is true for $k$ vertices. Then we need to find a monochromatic odd cycle in the $k+1$ coloring on $2^{t+1}+1$ vertices. I would guess there is some clever way to split the vertices into two, but I'm not sure how.

If anyone has a guiding hint, it would be appreciated.

Let's call the colour $1,2,\dots,r$.
Suppose that there is a $r$-colouring of $K_{2^r+1}$ with no monochromatic odd cycle. Consider the graph $G_r$ of the edges coloured with colour $r$. This graph is bipartite, say with bipartition $A$ and $B$ of the vertex set. We can assume $|A|\geq 2^{r-1}+1$.
This means that we can have a $(r-1)$-colouring of $K_{2^{r-1}+1}$ with no monochromatic odd cycle. This leads a contradiction if we do it recursively, since we cannot have $1$-colouring for $K_3$ with no monochromatic odd cycle.
Actually there is another part of this question which shows that the bound $2^r+1$ is tight, namely: there is a $r$-colouring of $K_{2^r}$ such that there is no monochromatic odd cycle. That can be constructed by recursively combined two $(r-1)$-coloured $K_{2^{r-1}}$ and colour the edges between them by colour $r$.
• Another way of thinking about it is that you want to cover the edges of the complete graph by bipartite graphs. If a graph $G=G_1 \cup G_2$, then $\chi(G) \leq \chi(G_1)\chi(G_2)$. Hence if a graph can be covered by $k$ bipartite graphs, then $\chi(G) \leq 2^k$. To cover $K_{2^r}$ by $r$ bipartite graphs, consider the $r$ partitions where in the $ith$ partition, vertices with $ith$ bit zero are in one part and those with $i$th bit one are in the other part. – Aravind Jul 7 '16 at 4:05