3
$\begingroup$

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.

  • 2
    Can anyone find a more direct proof, without all this case-working?2012-10-30

2 Answers 2

1

Another proof I found on http://staff.imsa.edu/~nprince/teachingfiles/S10/GTwA/:

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$.

  • 0
    thanks for the two solutions, I prefer this second one though.2012-10-31
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$.