# Prove that there exists a monochromatic shape in $K_{17}$ with each edge being one of 4 different colours

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. :(

• what do you mean by "monochromatic shape"?
– Mike
Jan 21, 2021 at 4:20
• A monochromatic shape has all it's edges the same colour. Jan 21, 2021 at 4:29
• Okay, but what are the edges of a shape? Is it a clique? a cycle? a path? a star? a lobster? a caterpillar? Jan 21, 2021 at 4:31
• I think what you mean, then, is you're looking for a monochromatic odd cycle: for some vertices $v_1, v_2, \dots, v_{2k+1}$, the edges $v_1 v_2, v_2 v_3, \dots, v_{2k} v_{2k+1}$ and $v_{2k+1} v_1$ are all the same color. Is that right? People don't usually talk about "pentagons" or "heptagons" with graphs. Jan 21, 2021 at 4:36
• What is a "complete graph of a 17-sided shape?" Are you referring to $K_{17}$? Jan 21, 2021 at 4:38

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.

• Instead of using induction can't you just use the pigeonhole principle to say that there are two vertices $u,v$ that are on the same side of each of the $k$ bipartitions so the edge $uv$ can't have any color?
– bof
Jan 21, 2021 at 5:06
• That works, but when I thought about writing it out, I felt like it would take more words. Jan 21, 2021 at 5:08