Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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|cite|improve this answer

Your Answer

 
discard

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