We colored the edges of K6 red or blue Prove that there is a

We colored the edges of K₆ red or blue. Prove that there is a cycle of length four with monochromatic edges.

Solution

Since each vertex of K6 has degree 5, each vertex must have at least 3 edges of the same color. Call a vertex red if it has at least 3 red edges and blue if it has at least 3 blue edges. Since there are 6vertices altogether, there must be at least 3 vertices of the same color; suppose that there are at least 3 red vertices, say u,v and w. There are several cases.

First suppose that all three of the edges uv,vw and uw are blue. Let the other 3 vertices be x,y and z. The vertices u,v, and w are red, so every edge from one of u,v, and w to x,y, or z must be red, and u,x,v,y,u is a red 4 cycle.

Thus, we may assume that two of these red vertices, say u and v, are connected by a red edge. Each of them is connected by red edges to (at least) 2 other vertices. Say u is connected by red edges to u₁ and u₂, and v is connected by red edges to v₁ and v₂.

The remaining possibility is that the sets {u₁,u₂} and {v₁,v₂} have exactly one element in common; say u₁=v₁. I’ll leave it to you to check that if any of the edges u₁u₂,u₁v_2,u₂v₂,uv₂, or vu₂ is red, then there is a red 4-cycle, so we may assume that all of these edges are blue. This means that u₂ and v₂ are blue vertices, so either w=u₁or w is the sixth vertex, different from all of u,v,u₁,u₂, and v₂.

If w=u₁, let x be the sixth vertex; the edge wx must be red, since w is a red vertex, and wu₂and wv₂ are blue. If any of the edges from x to u,v,u₂, or v₂ is red, it’s easy to find a red 4-cycle, so assume that all are blue; then x,u₂,v₂,u,x is a blue 4-cycle.

If w is the sixth vertex, it has red edges to at least 3 of the vertices u,v,u₁,u₂, and v₂. In particular, it must have a red edge to at least one of the vertices u₁,u₂, and v₂. Suppose that wu₁ is red; you can check that no matter which of the edges wu,wv,wu₂, or wv₂ is red, there is a red 4-cycle. (E.g., if wu is red, we can use w,u,v,u₁,w, and if wu₂ is red, we can use w,u₂,u,u₁,w.) Thus, we may assume that wu₁ is blue and wu₂, say, is red. But then either wvis red, and we have a red 4-cycle w,u₂,u,v,w or wv is blue, and we have a blue 4-cycle w,u₁,u₂,v,w.