1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ what do you mean by "monochromatic shape"? $\endgroup$
    – Mike
    Jan 21, 2021 at 4:20
  • $\begingroup$ A monochromatic shape has all it's edges the same colour. $\endgroup$
    – Grayson Spencer
    Jan 21, 2021 at 4:29
  • $\begingroup$ Okay, but what are the edges of a shape? Is it a clique? a cycle? a path? a star? a lobster? a caterpillar? $\endgroup$
    – Misha Lavrov
    Jan 21, 2021 at 4:31
  • $\begingroup$ 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. $\endgroup$
    – Misha Lavrov
    Jan 21, 2021 at 4:36
  • $\begingroup$ What is a "complete graph of a 17-sided shape?" Are you referring to $K_{17}$? $\endgroup$
    – William
    Jan 21, 2021 at 4:38

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – bof
    Jan 21, 2021 at 5:06
  • 1
    $\begingroup$ That works, but when I thought about writing it out, I felt like it would take more words. $\endgroup$
    – Misha Lavrov
    Jan 21, 2021 at 5:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .