Prove that there exists a monochromatic odd cycle (thanks to Misha Lavrov for correcting me) in a complete graph of a 17-sided shape ($K_{17}$) with each edge being one of 4 different colours
I've done some work on Ramsey theory on this question, but I haven't gotten very far. I've found that for any point A, there are 16 edges. At least 1 colour (say red) has 4 or more edges from Point to another that are that colour. There are then 6 remaining edges that connects those 4 points. If any of those edges are red, then there is a triangle, so we are finished.
However, if none of those edges are red, ten there is 3 possible colours remaining. If any of those colours connects 3 flights or 5 flights, we are done. However, worst case it that each colour only connects 2, which doesn't really prove anything...
P.S. For the record, this is from a textbook that I've been using to study for an exam, but they don't have answers. :(
The key to this problem is the following result: a graph that does not contain any odd cycle is bipartite. That is, its vertices can be partitioned into two sets $A$ and $B$ such that all edges go between $A$ and $B$.
We can prove a more general claim: if the complete graph on $2^k+1$ vertices is edge-colored with $k$ colors, then there is a monochromatic odd cycle.
This is easy for $k=1$: the complete graph on $3$ vertices contains an odd cycle, and there is only one color. From there, induct on $k$.
Pick your favorite color, and consider the subgraph of all edges of that color. If there is no odd cycle of that color, then it is bipartite: we can split the $2^k+1$ vertices into two sets $A,B$ such that all edges of your favorite color go between $A$ and $B$.
One of $A$ or $B$ (without loss of generality, $A$) has size at least $\lceil \frac{2^k+1}{2}\rceil = 2^{k-1}+1$. Within $A$, your favorite color never gets used. So the coloring restricted to $2^{k-1}+1$ vertices of $A$ only uses $k-1$ colors, and by the inductive hypothesis, there is a monochromatic odd cycle there.