Existence of a monochromatic $C_{2k + 1}$ implies the existence of a monochromatic $C_{2k}$.

85 Views Asked by At

Theorem: Consider a 2-coloring of the edges of the complete graph $K_n$, and let $k \geq 3$. Prove that if there is a monochromatic $C_{2k + 1}$, then there is a monochromatic $C_{2k}$.

Attempt: Consider a blue cycle $C_{2k+1}=v_1v_2...v_{2k+1}v_1$, and assume that there is no red $C_{2k}$. We can force some edges to be red. For example, all edges $v_iv_{i+2}$ must be red. I feel I can also force $v_iv_{i+3}$ to be red for at least one $i$. WLOG, consider $i=2k-2$. I mean $c_{2k-2}v_1$ is red. Skipping $v_{2k}$ as shown below, we can get a red $C_{2k}$. $$v_1v_3...v_{2k+1}v_2v_4...v_{2k-2}v_1$$.

I would like to ask if there is a better idea. Thank you.

1

There are 1 best solutions below

3
On

Note that it is enough to show the theorem holds for $n=2k+1$. Let $v_0, \dots, v_{2k}$ be a cyclic ordering of the vertices of our monochromatic, say blue, cycle of length $2k+1$. We show that there is a monochromatic cycle of length $2k$.

Observe that if any edge of the form $v_iv_{i+2}$ (where the indices are taken modulo $2k+1$) is blue, we form a blue $C_{2k}$ using all vertices except $v_{i+1}$. Hence, we assume these are red. These red edges form a red $C_{2k+1}$ since $2$ and $2k+1$ are coprime. Analogously, if any edge of the form $v_iv_{i+4}$ is red, we form a red $C_{2k}$ using all vertices except $v_{i+2}$. Thus, all such edges are blue, and form another blue $C_{2k+1}$. Note that we are implicitly using the fact that $k\geq 3$ here, since if $k=2$, the two blue $C_{2k+1}$ are the same, since $-1\equiv 4\mod 5$.

If the edge $v_0v_3$ is blue, then

$$v_0v_3v_2v_1v_5v_6v_7\dots v_{2k}$$

forms a blue $C_{2k}$, using all vertices but $v_4$. Hence, by symmetry, any edge of the form $v_iv_{i+3}$ is red. But then

$$v_0v_3v_6v_8v_{10}\dots v_{2k}v_1v_{2k-1}v_{2k-3}\dots v_9v_7v_5v_2$$

forms a red $C_{2k}$ using all vertices but $v_4$, as desired.