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

Question

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.

Answer 1

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

Answer 2

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:

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.

Answer 3

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.

Answer 4

Suppose there is no monochromatic $C_4$. Then for each pair of vertices $a,b$ we have $|N(a)\cap N(b)|\leq 1$ and $|N'(a)\cap N'(b)|\leq 1$. On the other hand every element is connected to $$d={x\choose 2}+{y\choose 2}$$ pairs of vertices (in $G$ and $G'$), so $x+y=13$. By Jensen inequality we have $$d\geq {{1\over 2}13^2-13\over 2}={143\over 4}\implies d\geq 36 $$

so we have $$2 {14\choose 2}\geq 14\cdot 36$$ which is clear contradiction.

---

We have stronger result: If we go from 14 to 8 we get $d\geq 9$ so we get $$2 {8\choose 2}\geq 8\cdot 9$$ which is again a contradiction. So $K_8$ contains monochromatic $C_4$.