2
$\begingroup$

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.

$\endgroup$

closed as off-topic by zz20s, choco_addicted, Claude Leibovici, John B, Jean-Claude Arbaut Apr 22 '16 at 19:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – zz20s, Claude Leibovici, John B, Jean-Claude Arbaut
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ Do not vandalize your post after it is answered. It is extremely rude to those who put the effort into answering. $\endgroup$ – user296602 Apr 22 '16 at 4:46
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
-3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The result is in fact correct, and in the picture at your link Bryan, Charlie, David, and Fred form a blue $4$-cycle. $\endgroup$ – Brian M. Scott Apr 20 '16 at 23:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.