2
$\begingroup$

This question is from Problem Solving Strategies by Engel, Chapter 4 question 50.

If $K_{14}$ is colored with two colors, there will be a monochromatic quadrangle.

Here, $K_{14}$ is the complete graph with 14 vertices, a coloring means to assign each edge a color (lets say either red or blue) and I am assuming quadrangle means a cycle of length 4.

I know the technique to prove that $R(3,3) = 6$ (the Ramsey number), and I tried to apply it but with no success. For example, if I have a red path of length 3, then I can force the last edge to be blue. I also started by considering that each vertex has 13 neighbors, so each vertex has either more red or blue edges. So there exists at least 7 vertices, each with at least 7 edges of the same color. But I don't see a way to proceed.

$\endgroup$
2
$\begingroup$

Let's try to avoid a monochromatic quadrangle ($4$-cycle):

As you noted each vertex has at least $7$ incident edges with the same color. Let $x$ be a vertex and let $a_1$, $a_2$, $a_3$, $a_4$ be four vertices for which the edges from $x$ to each $a_i$ are all the same color ($i=1,2,3,4$). Without loss of generality, we may assume that the color of those edges is red.

Now let $y$ be a different vertex (not $x$ and not any of $a_1,...,a_4$). At least three of the edges $(y,a_1), (y,a_2), (y,a_3), (y,a_4)$ must be blue. (If any two are red, you get a red quadrangle using $x,a_i,y,a_j$ where the edges $(y,a_i)$ and $(y,a_j)$ are red.) Without loss of generality, we may assume $(y,a_1), (y,a_2), (y,a_3)$ are all blue edges.

If the edge from $a_1$ to $a_2$ is red, then the edge from $a_2$ to $a_3$ must be blue (otherwise $x,a_1,a_2,a_3$ is a red quadrangle). But then the edge from $a_1$ to $a_3$ will complete a monochromatic quadrangle (if red: $x,a_2,a_1,a_3$; if blue: $y,a_1,a_3,a_2$).

Similarly if the edge from $a_1$ to $a_2$ is blue, you will again get a monochromatic quadrangle.

Note: It appears to me that this argument could be used to show that a monochromatic quadrangle must exist on an edge 2-colored $K_9$.

$\endgroup$
  • $\begingroup$ That is a really nice proof! Seems like the crux move is considering the vertices $x$ and $y$, each with 3 edges of their respective colors connecting to the three $a_i$. Thanks! $\endgroup$ – eatfood May 10 at 15:26
  • 1
    $\begingroup$ This also works for $K_7$, right? $\endgroup$ – Santana Afton May 10 at 15:35
  • $\begingroup$ I don't think it works for $K_7$ because you need the $x$ and $y$ vertices separate from $7$ other vertices. $\endgroup$ – paw88789 May 10 at 15:50
  • 1
    $\begingroup$ It sure does work for $K_7$. If you $2$-color the edges of $K_7$ there must (by pigeonhole & parity) be a vertex with $4$ incident edges of the same color; say $xa_1$, $xa_2$, $xa_3$, $xa_4$ are distinct red edges. Choose a vertex $y\notin\{x,a_1,a_2,a_3,a_4\}$, etc. @SantanaAfton This is what you had in mind, right? $\endgroup$ – bof May 11 at 5:07
  • 1
    $\begingroup$ @bof Yup! Exactly. $\endgroup$ – Santana Afton May 11 at 5:14
2
$\begingroup$

A sharper result shows that any $2$-coloring of $K_6$ contains a monochromatic $C_4$.

We know $R(3,3)=6$, so any $2$-coloring of $K_6$ contains a monochromatic triangle. Let $\{x,y,z\}$ be the vertices of the triangle, and without loss of generality let red be the color of edges $xy, xz, yz$.

If there is another vertex $w$ with red edges to at least two vertices among $\{x,y,z\}$, then we get a red $C_4$. Say $wx$ and $wy$ are red: then the edges $wx, xz, zy, yw$ form a red cycle.

Otherwise, each of the three vertices outside $\{x,y,z\}$ has at most one red edge to $\{x,y,z\}$ - and at least two blue edges to $\{x,y,z\}$. If there are two vertices $w_1, w_2$ with blue edges to the same two vertices among $\{x,y,z\}$, then we get a blue $C_4$. Say $w_1x, w_1y, w_2x, w_2y$ are blue: then the edges $w_1x, xw_2, w_2y, yw_1$ form a blue cycle.

The remaining possibility is that the other three vertices all have exactly two blue edges to $\{x,y,z\}$, and it's a different set of blue edges for each one. We can label the remaining vertices $\{x', y', z'\}$ such that edges $xx', yy', zz'$ are red while $xy', xz', yx', yz', zx', zy'$ are blue, getting the partial coloring below:

enter image description here

Now we look at the colors of the three remaining edges $x'y', x'z', y'z'$.

  • If $x'y'$ is red, then the edges $x'y', y'y, yx, xx'$ form a red cycle.
  • If $y'z'$ is red, then the edges $y'z', z'z, zy, yy'$ form a red cycle.
  • If $x'y'$ and $y'z'$ are both blue, then the edges $x'y', y'z', z'y, yx'$ form a blue cycle.
$\endgroup$
2
$\begingroup$

The complete graph $K_{14}$ is much bigger than needed for this result; here are three proper subgraphs with the same property.


I. Every $2$-coloring of the complete bipartite graph $K_{3,7}$ contains a monochromatic $C_4$.

Let $K_{3,7}$ have partite sets $V_1,V_2$ with $|V_1|=3$ and $|V_2|=7$. Each vertex in $V_2$ is joined by edges of one color to two vertices in $V_1$. By the pigeonhole principle, two vertices in $V_2$ are joined by edges of the same color to the same two vertices in $V_1$.


II. Every $2$-coloring of the complete graph $K_6$ contains a monochromatic $C_4$. (This was shown in Misha Lavrov's answer; the following argument is perhaps slightly simpler.)

We may assume that there is a vertex $x$ which is incident with at most two blue edges. In fact, we may assume that $x$ is incident with exactly two blue edges; otherwise $x$ would be incident with four red edges, call them $xa_1$, $xa_2$, $xa_3$, $xa_4$, and then we could consider a vertex $y\notin\{x,a_1,a_2,a_3,a_4\}$ and proceed as in paw88789's answer. (It may be even easier to observe that the subgraph induced by $\{a_1,a_2,a_3,a_4\}$ contains either a red $P_3$ or a blue $C_4$.)

So let $x$ be incident with exactly two blue edges, $xy$ and $xz$. If one of the remaining three vertices is joined by blue to both $y$ and $z$, then we have a blue $C_4$. On the other hand, if each of those three vertices is joined by red to a vertex in $\{y,z\}$, then two of them are joined by red to the same vertex in $\{y,z\}$, and also to $x$, making a red $C_4$.


III. Every $2$-coloring of the complete bipartite graph $K_{5,5}$ contains a monochromatic $C_4$.

The proof is left as an exercise for the reader.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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