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$.