The Question Behind \(R(3,3)\)
Suppose every edge joining a group of people is marked either red or blue. How large must the group be to guarantee three people whose three pairwise edges all have the same color? The answer is six. The proof is short once the edges incident to one vertex are organized into red and blue neighborhoods, but the lower bound needs a carefully checked coloring on five vertices.
Here \(K_n\) has every possible edge between distinct vertices. Thus \(K_6\) has \(\binom{6}{2}=6\cdot5/2=15\) edges, and \(K_5\) has \(\binom{5}{2}=5\cdot4/2=10\) edges. To prove the exact value, we need both parts: every coloring of \(K_6\) has a monochromatic triangle, and at least one coloring of \(K_5\) does not.
What a Vertex Neighborhood Guarantees
For a vertex \(v\), its red neighborhood is the set of vertices joined to \(v\) by red edges; its blue neighborhood is defined in the same way. In \(K_6\), each vertex has five incident edges, so one color occurs on at least three of them. The next lemma records precisely why that is enough.
Proof. Let \(v\) be a vertex with at least three incident edges of the same color, and choose three distinct neighbors \(a,b,c\) joined to \(v\) in that color. First suppose those three edges are red. If any of \(ab,ac,bc\) is red, that edge together with the two red edges from its endpoints to \(v\) forms a red triangle. If none is red, then all three edges \(ab,ac,bc\) are blue, so \(a,b,c\) form a blue triangle. If the three edges from \(v\) are blue instead, the same reasoning with the color names exchanged gives either a blue triangle through \(v\) or a red triangle on \(a,b,c\). Thus a monochromatic triangle exists in either case. \(\square\)
There are five incident edges at any chosen vertex of \(K_6\). If at most two were red and at most two were blue, there would be at most \(2+2=4\) incident edges, contradicting the total of five. Hence at least three have one color, and the lemma applies. This proves the upper bound: every red-blue coloring of \(K_6\) contains a monochromatic triangle.
Worked Example: A Red Edge Inside the Red Neighborhood
Take \(V=\{1,2,3,4,5,6\}\). Color the edges \(12,13,14,24,35,46\) red, and color every other edge of \(K_6\) blue. The total number of edges is \(\binom{6}{2}=6\cdot5/2=15\). There are six listed red edges, so the number of blue edges is \(15-6=9\).
At vertex \(1\), the red neighbors are \(2,3,4\): the listed edges \(12,13,14\) are red. Among those three neighbors, \(24\) is red. Therefore \(1,2,4\) form a red triangle, since \(12\), \(14\), and \(24\) are all red.
Check: The three edges of the claimed triangle are exactly \(12\), \(14\), and \(24\), and each occurs in the red edge list. The neighborhood argument succeeds at its first branch: a red edge among three red neighbors completes a red triangle with the chosen vertex.
Worked Example: No Red Edge Among Three Red Neighbors
Again take \(V=\{1,2,3,4,5,6\}\). Color \(12,13,14,15,16\) red and every other edge blue. The red edge list has five edges, while \(K_6\) has \(15\) edges, so there are \(15-5=10\) blue edges.
The red neighbors of \(1\) are \(2,3,4,5,6\). In particular, choose \(2,3,4\). The edges \(23\), \(24\), and \(34\) are not in the red list, so each is blue. Thus \(2,3,4\) form a blue triangle. This is the other branch of the argument: when the three chosen red neighbors have no red edge between them, their three pairwise edges are all blue.
Check: The blue edges \(23,24,34\) are all among the ten edges not incident to \(1\). They are therefore blue by the definition of this coloring, and all three edges of the claimed triangle have been verified.
Why Five Vertices Do Not Suffice
The upper-bound argument depends on having five edges at the selected vertex. To show that six is the exact threshold, we now color all ten edges of \(K_5\) and check that neither color contains a triangle.
Worked Example: A Coloring of \(K_5\) Without a Monochromatic Triangle
Let \(V=\{1,2,3,4,5\}\). Color the edges \(12,23,34,45,15\) red, and color all other edges blue. Since \(K_5\) has \(\binom{5}{2}=5\cdot4/2=10\) edges, and five have been listed as red, the other \(10-5=5\) edges are \(13,14,24,25,35\), all blue.
The red edges form the cycle \(1,2,3,4,5,1\). The blue edges form the cycle \(1,3,5,2,4,1\). To check that neither cycle contains a triangle, list the two same-color neighbors of each vertex. In the red cycle, these pairs are \(\{2,5\}\), \(\{1,3\}\), \(\{2,4\}\), \(\{3,5\}\), and \(\{4,1\}\), for vertices \(1,2,3,4,5\) respectively. None of these pairs is joined by a red edge: the red edge list is exactly the five consecutive edges of the displayed cycle.
For blue, the cycle order is \(1,3,5,2,4,1\). The pairs of blue neighbors, in vertex order \(1,2,3,4,5\), are \(\{3,4\}\), \(\{5,4\}\), \(\{1,5\}\), \(\{2,1\}\), and \(\{3,2\}\). None is joined by a blue edge: each pair consists of vertices two steps apart in the displayed five-cycle, whereas the blue edges are exactly its consecutive edges. A triangle would require a vertex whose two neighbors are joined by an edge of that same color. The checks rule this out for both colors.
Check: The red list and blue list are disjoint and together contain \(5+5=10\) edges, the full edge count of \(K_5\). The two lists therefore specify every edge exactly once, and the neighbor checks show that this coloring has no monochromatic triangle.
The Exact Value
Proof. The neighborhood argument proves that every red-blue coloring of \(K_6\) contains a monochromatic triangle. Therefore the defining property holds for \(n=6\). The displayed coloring of \(K_5\) has no monochromatic triangle, so the property does not hold for \(n=5\). It also cannot hold for any smaller positive \(n\): if every coloring of some \(K_n\) had a monochromatic triangle, then every coloring of a larger complete graph would have one as well, because restricting that coloring to any \(n\) vertices gives a coloring of \(K_n\). In particular, a property holding at a smaller \(n\) would force it to hold at \(5\), contrary to the explicit coloring. Thus the least \(n\) with the property is \(6\). \(\square\)
This conclusion separates the roles of the two constructions. The neighborhood argument is universal: it covers every possible coloring on six vertices without listing them. The five-vertex example is a certificate that the universal guarantee cannot be lowered to five. Neither part alone establishes the exact value.
A Common Pitfall
Using the \(K_6\) count on \(K_5\). A common mistake is to say that at a vertex of \(K_5\), at least three of the incident edges have the same color. That count is incorrect: a vertex of \(K_5\) has only four incident edges, and a split of two red and two blue is possible. In the coloring above, vertex \(1\) has red neighbors \(2,5\) and blue neighbors \(3,4\). The red edge \(25\) is absent, and the blue edge \(34\) is absent, so neither pair completes a monochromatic triangle through \(1\). The correction is to use the five-edge pigeonhole count only in \(K_6\); the explicit coloring shows why four incident edges do not give the same conclusion.
The proof is a small example of a broader Ramsey-theoretic pattern: a local count forces a structure once a set is large enough, while a carefully chosen coloring shows that the threshold is sharp. Here the local set is the neighborhood of one vertex, and the structure forced is a triangle whose three edges have the same color.
Check Your Understanding
Use the neighborhood argument and the explicit coloring to check both the logic and the sharpness of the result.
- Why must five edges incident to a vertex include at least three of one color?
- If \(v\) has three red neighbors \(a,b,c\), what monochromatic triangle follows when \(ab\) is red? What follows if all three edges among \(a,b,c\) are blue?
- In the \(K_5\) coloring, list the blue edges and verify that they form the cycle \(1,3,5,2,4,1\).
- Why does a coloring of \(K_5\) without a monochromatic triangle rule out the defining property at every smaller positive number of vertices?
- For a vertex of \(K_5\), explain why the same pigeonhole argument used for \(K_6\) does not guarantee three neighbors joined by edges of one color.