Three Colors and the Triangle Threshold
In a two-coloring of the edges of a sufficiently large complete graph, one can force a monochromatic triangle. With three colors, the same question asks how many vertices guarantee a triangle whose three edges all have one color. The neighborhood recurrence gives a short upper bound: \(R(3,3,3)\le17\). To understand what a matching lower bound would require, we will also examine the constraints on a coloring of \(K_{16}\) with no monochromatic triangle.
Thus \(R(3,3,3)\) is the least order that guarantees a monochromatic triangle in every three-coloring of a complete graph. A coloring of \(K_{16}\) with no monochromatic triangle would prove \(R(3,3,3)\ge17\); an upper-bound argument must show that every coloring of \(K_{17}\) has such a triangle.
The Neighborhood Recurrence
For integers \(a,b,c\ge2\), the three-color recurrence is
The subtraction by \(1\) comes from counting the neighbors of one fixed vertex: the vertex itself is not in any of the three color classes of its neighborhood.
Proof. Write \(A=R(a-1,b,c)\), \(B=R(a,b-1,c)\), and \(C=R(a,b,c-1)\), and consider any three-coloring of \(K_{A+B+C-1}\). Fix a vertex \(v\). Partition its neighbors into \(N_R(v)\), \(N_B(v)\), and \(N_G(v)\), according to the color of their edge to \(v\).
If \(|N_R(v)|\ge A\), the coloring induced on those \(A\) vertices contains either a red \(K_{a-1}\), a blue \(K_b\), or a green \(K_c\), by the definition of \(A\). In the first case, adjoining \(v\) gives a red \(K_a\); in either other case, the required blue or green clique is already present. Therefore, if the whole graph has none of the three target cliques, then \(|N_R(v)|\le A-1\). The same argument using \(B\) and \(C\) gives \(|N_B(v)|\le B-1\) and \(|N_G(v)|\le C-1\).
But \(v\) has \(A+B+C-2\) neighbors, whereas these three bounds give at most \((A-1)+(B-1)+(C-1)=A+B+C-3\) neighbors. This is a contradiction. Consequently every coloring of \(K_{A+B+C-1}\) contains a target clique, proving the recurrence. \(\square\)
Worked Example: The Boundary Value R(2,3,3)
The recurrence for the triangle bound uses \(R(2,3,3)\). We verify that this value is \(6\), using the exact two-color result \(R(3,3)=6\).
For the upper bound, take any three-coloring of \(K_6\). If it has a red edge, that edge is already a red \(K_2\). If it has no red edge, all edges are blue or green, and the exact value \(R(3,3)=6\) guarantees a blue or green triangle. Thus \(R(2,3,3)\le6\).
For the reverse inequality, use vertices \(\{0,1,2,3,4\}\), put no edges in red, and color the edges of \(K_5\) as follows:
The blue edges form the cycle \(0,1,2,3,4,0\). The green edges form the cycle \(0,2,4,1,3,0\). Each cycle has five edges, and the two edge sets are disjoint, so together they contain all \(5+5=10\) edges of \(K_5\). Neither color contains a triangle, and there is no red edge. This coloring avoids all three targets, so \(R(2,3,3)>5\). Combining the bounds gives \(R(2,3,3)=6\).
Check: a red \(K_2\) would be a red edge, and the construction has no red edges. The blue and green graphs are each a 5-cycle, not a triangle. Hence the coloring really does avoid every target in the definition of \(R(2,3,3)\).
Applying the Recurrence
The exact two-color value needed below is \(R(3,3)=6\), established in the earlier material on exact Ramsey numbers. By symmetry of the colors, the three terms on the right side of the recurrence for \(R(3,3,3)\) are equal to \(R(2,3,3)\). Substitution therefore gives the desired bound.
Worked Example: Evaluating the Three-Color Recurrence
Set \(a=b=c=3\) in the recurrence. The terms are \(R(2,3,3)\), \(R(3,2,3)\), and \(R(3,3,2)\). Relabeling colors does not change a Ramsey number, so each is \(R(2,3,3)=6\). Hence
The arithmetic is \(6+6+6=18\), followed by subtracting \(1\), giving \(17\). The \(-1\) is part of the recurrence; omitting it would give a weaker bound of \(18\).
Check: the three recurrence terms correspond respectively to lowering the red, blue, and green target from a triangle to an edge. Each resulting threshold is \(6\), so all three terms have been included.
Proof. Apply the proved recurrence with \(a=b=c=3\). Each term is \(R(2,3,3)=6\), so \(R(3,3,3)\le6+6+6-1=17\). By the definition of the Ramsey number, every three-coloring of \(K_{17}\) contains a red, blue, or green triangle. \(\square\)
What a Lower-Bound Coloring Must Avoid
The upper bound alone does not prove that \(R(3,3,3)=17\). To establish the matching lower bound, one must give an actual coloring of \(K_{16}\) in which no color contains a triangle. In particular, it is not enough for each color to avoid some other target: every one of the three color classes must be triangle-free.
Worked Example: Necessary Conditions on a Coloring of K16
Suppose the edges of \(K_{16}\) have been colored red, blue and green with no monochromatic triangle. Fix a vertex \(v\). There are \(15\) edges incident with \(v\). For each color \(i\), let \(N_i(v)\) be the set of neighbors joined to \(v\) by an edge of color \(i\).
We claim that \(|N_i(v)|\le5\) for each color \(i\). If, for example, \(|N_{\text{red}}(v)|\ge6\), the edges among six red-neighbors cannot be red: a red edge between two of them, together with their two red edges to \(v\), would form a red triangle. Those six vertices are therefore colored only blue and green internally. Since \(R(3,3)=6\), they contain a blue or green triangle, contradicting the assumed absence of monochromatic triangles. The same reasoning applies to blue and green neighborhoods.
The three sets \(N_{\text{red}}(v)\), \(N_{\text{blue}}(v)\), and \(N_{\text{green}}(v)\) partition the \(15\) neighbors. Each has size at most \(5\), so their sizes must all equal \(5\): their sum is \(15\), and the sum of their three upper bounds is also \(5+5+5=15\).
This holds at every vertex. Thus each color has degree \(5\) at every vertex, and the number of edges of each color is \(16\cdot5/2=40\): the degree sum is \(16\cdot5=80\), and each edge contributes \(2\). The three color classes together have \(3\cdot40=120\) edges, exactly the number in \(K_{16}\), since \(16\cdot15/2=120\).
Check: these counts are necessary, not sufficient. A coloring with three 5-regular color graphs could still contain a monochromatic triangle. A valid lower-bound certificate must also verify that each of its three color graphs has no triangle.
A Common Pitfall About Lower Bounds
A coloring that avoids monochromatic triangles in two colors need not be a valid lower-bound coloring for \(R(2,3,3)\): it must also avoid a red edge. For example, the five-cycle construction above is a valid two-coloring of \(K_5\) showing \(R(3,3)>5\) when its two cycles are called red and blue. But under those names it contains red edges, so it does not avoid the red \(K_2\) target in \(R(2,3,3)\).
The correction is to use no red edges: color one of the five-cycles blue and the complementary five-cycle green. This is exactly the \(K_5\) construction used to prove \(R(2,3,3)>5\). The targets in the definition determine what a lower-bound coloring must avoid; changing the target from a triangle to an edge makes even a single edge in that color disqualifying.
For \(R(3,3,3)\), the same discipline applies: a lower-bound witness on \(16\) vertices must avoid a monochromatic triangle in red, blue, and green. The recurrence proves the upper bound without supplying that witness. Together, the recurrence and the necessary conditions above show both how the bound \(17\) arises and what must be checked in any attempt to match it from below.
Check Your Understanding
Use the definitions and arguments in this tutorial to answer the following.
- In the recurrence for \(R(a,b,c)\), why is the number of neighbors of the fixed vertex \(A+B+C-2\), rather than \(A+B+C-1\)?
- Explain why a red neighborhood of size \(6\) would force a monochromatic triangle when \(R(3,3)=6\).
- Why does a coloring of \(K_{16}\) with no monochromatic triangle need exactly five incident edges of each color at every vertex?
- How many edges of each color must such a \(K_{16}\) coloring have? Show the degree-sum calculation.
- Why does the red-and-blue five-cycle coloring of \(K_5\) fail to certify \(R(2,3,3)>5\), and what recoloring fixes it?