# Six points connected in pairs by coloured lines

Six points are connected in pairs by lines each of which is either red or blue. Every pair of points is joined. Determine whether there must be a closed path having four sides all of the same colour. A path is closed if it begins and ends at the same point.

-
There are 15 lines, so there must be at least 8 lines the same color. I can't see any way to draw 8 lines without forming a 4-cycle. – Gerry Myerson Oct 30 '12 at 12:07
Can anyone find a more direct proof, without all this case-working? – barto Oct 30 '12 at 13:19

Let the edges of $K_6$ be $2$-colored, and let $v\in V(K_6)$. Suppose that neither color contains a monochromatic $C_4$. Notice that if $u$ and $v$ are vertices such that $u$ sends edges of color $1$ to every vertex of $W=\{w_1,w_2,w_3\}$ and $v$ sends edges of color $2$ to every vertex of $W$, then regardless of how the edges among the $w_i$'s are colored, there will be a monochromatic $C_4$. If $v$ is incident to at least $4$ edges of color $i$, then there must be a $u$ and a set $W$ such that $u$ sends three edges of color $3-i$ and $v$ sends three edges of color $i$ to $W$, and we are done by the previous sentence. Therefore, we can assume (by symmetry) that $v$ is incident to exactly $3$ edges of color $1$. Call the set of neighbors of $v$ in color $1$ $W$. Let $\{x,y\}=V(G)-W-v$. If $x$ and $y$ have a common neighbor in color $2$ in the set $W$, then there is a monochromatic $C_4$ in color $2$. Otherwise, one of $x$ and $y$ has sends two edges of color $1$ into $W$, yielding a $C_4$ in color $1$.
Assume that the red is the most represented color. So there are at least 8 red lines. If there is not a blue 4-cycle among $A,B,C,D$, there must be at least 2 red lines among $A,B,C,D$ sharing a common vertex, say $AB$ and $AC$. Between $\{E,F\}$ and $\{A,B,C,D\}$ there are 8 lines: at least $5$ of them must be red. Assume that $EF$ is red. If all the $4$ lines between $E$ (or $F$) and $\{A,B,C,D\}$ are red, $ACEB$ ($ACFB$) is a red 4-cycle. So we can assume that there are $3$ red lines between $E$ and $\{A,B,C,D\}$ (and we can assume that they are $EA,EC,ED$) and $2$ red lines between $F$ and $\{A,B,C,D\}$, so at least $1$ red line between $F$ and $\{A,B,C\}$, completing one of the following $4$-cycles: $ABFE$,$AFEC$,$ACFE$. If $EF$ is blue, then there are exactly $3$ red lines between $F$ and $\{A,B,C,D\}$: $FA,FB,FD$, completing the $4$-cycle $AFDE$.
This proves that there is a monochromatic $C_4$ in any $2$-coloring of the edges of $K_6$.