Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
Can anyone find a more direct proof, without all this case-working? –  barto Oct 30 '12 at 13:19

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
thanks for the two solutions, I prefer this second one though. –  user31280 Oct 31 '12 at 13:32

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.