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

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.

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.

• 4@Aqua A graph on $6$ vertices may contain as many as $9$ edges without containing a triangle, namely $K_{3,3}$.
– bof
Aug 15, 2021 at 22:30
• So what? What's your point?
– bof
Aug 15, 2021 at 22:39

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

• 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! May 10, 2019 at 15:26
• This also works for $K_7$, right? May 10, 2019 at 15:35
• I don't think it works for $K_7$ because you need the $x$ and $y$ vertices separate from $7$ other vertices. May 10, 2019 at 15:50
• 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?
– bof
May 11, 2019 at 5:07
• @bof Yup! Exactly. May 11, 2019 at 5:14

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.

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