Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges. Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges.
Attempt: I know that i have to...
prove that there must be TWO vertices with “red-degree” at least 3, or two with "blue-degree" at least 3. Call these U and V. (We'll assume we're in the red case; the blue case is similar.) Now, ask if they’re connected by a red edge, and how many red-adjacent neighbors they share. If you analyze this, there should be only a few cases to consider – and each should be relatively straightforward. For each case, you’ll show either that that case can’t actually happen in $K_6$, or that it gives rise to a monochromatic 4-cycle.
 A: I’ll do most of it, leaving a few details for you to check. It’s very helpful to make diagrams for the various cases.
Since each vertex of $K_6$ 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 $6$ vertices 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_1$ and $u_2$, and $v$ is connected by red edges to $v_1$ and $v_2$.


*

*If $\{u_1,u_2\}=\{v_1,v_2\}$, we may assume that $u_1=v_1$ and $u_2=v_2$. In this case $u,u_1,v,u_2,u$ is a red $4$-cycle.  

*If $\{u_1,u_2\}\cap\{v_1,v_2\}=\varnothing$, then the $6$ vertices $u,v,u_1,u_2,v_1,v_2$ are distinct, and one of them, say $u_1$, must be $w$. There are at least $3$ red edges at $w$, one of which is $uw$. If $wv_1$ is an edge, then $u,w,v_1,v,u$ is a red $4$-cycle, and similarly if $wv_2$ is a red edge. If neither $wv_1$ nor $wv_2$ is a red edge, then $wu_2$ and $wv$ must both be red, and $u,v,w,u_2,u$ is a red $4$-cycle.  


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


*

*If $w=u_1$, let $x$ be the sixth vertex; the edge $wx$ must be red, since $w$ is a red vertex, and $wu_2$ and $wv_2$ are blue. If any of the edges from $x$ to $u,v,u_2$, or $v_2$ is red, it’s easy to find a red $4$-cycle, so assume that all are blue; then $x,u_2,v_2,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_1,u_2$, and $v_2$. In particular, it must have a red edge to at least one of the vertices $u_1,u_2$, and $v_2$. Suppose that $wu_1$ is red; you can check that no matter which of the edges $wu,wv,wu_2$, or $wv_2$ is red, there is a red $4$-cycle. (E.g., if $wu$ is red, we can use $w,u,v,u_1,w$, and if $wu_2$ is red, we can use $w,u_2,u,u_1,w$.) Thus, we may assume that $wu_1$ is blue and $wu_2$, say, is red. But then either $wv$ is red, and we have a red $4$-cycle $w,u_2,u,v,w$, or $wv$ is blue, and we have a blue $4$-cycle $w,u_1,u_2,v,w$.
A: Fix a vertex and call its neighbours red or blue according to the edges leading to them. If there are $k$ red neighbours, the $5-k$ blue neighbours have at most $\binom{5-k}2$ red edges among each other. If a blue neighbour has more than one red edge to a red neighbour, we can form a red $4$-cycle; else, that's at most $5-k$ more red edges. If two red edges among the red neighbours share an endpoint, we can form a red $4$-cycle; else, that's at most $\left\lfloor\frac k2\right\rfloor$ more red edges, for a total of $k+\binom{5-k}2+5-k+\left\lfloor\frac k2\right\rfloor$ $=5+\binom{5-k}2+\left\lfloor\frac k2\right\rfloor$. This is $7$ for $k\ge3$, and we have $15$ edges, which leads to the contradiction that the majority edge colour is in the minority at each vertex.
A: I'm not sure if you're trying to prove the right thing, because there's not necessarily a monochromatic cycle of length 4 (see the picture). Actually, the Ramsey number R(3,3)=6, which means we can always find a monochromatic cycle of length 3.
You can refer to this link if you want to see the monochromatic 3-cycle proof.
https://plus.maths.org/content/friends-and-strangers
