The Ramsey Number \(R(3,4)\)
A Ramsey number records when a monochromatic pattern becomes unavoidable, regardless of how the edges are colored. Here the two patterns have different sizes: a red triangle and a blue complete graph on four vertices. The upper bound requires controlling what can happen around each vertex; the lower bound requires one coloring that avoids both patterns on eight vertices.
Thus \(R(3,4)=9\) means two statements must both hold: every red-blue coloring of \(K_9\) has a red triangle or a blue \(K_4\), and at least one coloring of \(K_8\) has neither. The first is an upper bound \(R(3,4)\le9\); the second is a lower bound \(R(3,4)>8\).
We will use the established value \(R(3,3)=6\). The particular consequence needed here is that every red-blue coloring of \(K_6\) contains a monochromatic triangle. For completeness, choose a vertex \(v\) of \(K_6\). At least three of its five incident edges have the same color. If three are red, consider their three other endpoints: a red edge between any pair makes a red triangle with \(v\), while if none is red, all three pairwise edges are blue and form a blue triangle. The same argument with the colors exchanged applies if three edges at \(v\) are blue.
Neighborhood Constraints on \(K_9\)
In a red-blue coloring, write \(R(v)\) for the vertices joined to \(v\) by red edges and \(B(v)\) for those joined to \(v\) by blue edges. These sets partition the other vertices, so for a vertex of \(K_9\), \(|R(v)|+|B(v)|=8\). We first show that any coloring avoiding both forbidden patterns would force every vertex to have exactly three red neighbors.
Proof. Fix any vertex \(v\). Suppose first that \(|B(v)|\ge6\), and select six vertices from \(B(v)\). Their edges contain a monochromatic triangle by the \(R(3,3)=6\) consequence above. A red triangle is forbidden by assumption. A blue triangle among these six vertices, together with \(v\), forms a blue \(K_4\), because all three edges from \(v\) to the triangle are blue. That too is forbidden. Hence \(|B(v)|\le5\), and therefore \(|R(v)|=8-|B(v)|\ge3\).
Now suppose \(|R(v)|\ge4\), and choose four red neighbors of \(v\). No pair among them can be joined by a red edge: that edge and the two red edges to \(v\) would make a red triangle. Since every pair is joined by exactly one of the two colors, all six edges among the four chosen vertices are blue. They form a blue \(K_4\), which is forbidden. Thus \(|R(v)|\le3\). Combining the two inequalities gives \(|R(v)|=3\). The argument applies to every vertex. \(\square\)
The two bounds use the neighborhoods in different ways. Six blue neighbors cannot occur because the \(R(3,3)\) property would produce a forbidden triangle in their coloring. Four red neighbors cannot occur because the absence of a red triangle forces all edges among them to be blue. The resulting exact degree is incompatible with having nine vertices.
Worked Example: The Six-Vertex Neighborhood Test
Let \(H\) be the red-blue coloring of the complete graph on \(\{x,1,2,3,4,5,6\}\) defined as follows. The edges \(x1,x2,x3,x4,x5,x6\) are blue. Among \(\{1,2,3,4,5,6\}\), the red edges are \(12,23,34,45,56,61\); every other edge is blue.
The internal blue edges are \(13,14,15,24,25,26,35,36,46\). In particular, \(13,15,35\) are all blue, so \(1,3,5\) form a blue triangle. Since \(x1,x3,x5\) are also blue, the four vertices \(\{x,1,3,5\}\) form a blue \(K_4\). This illustrates the upper-bound argument: a blue triangle within the blue neighborhood of a vertex immediately extends to a blue \(K_4\).
Check: The red edges form the cycle \(1,2,3,4,5,6,1\), which has no triangle. The blue \(K_4\) is verified by its six edges: \(x1,x3,x5,13,15,35\).
The Upper Bound
Proof. Suppose, to obtain a contradiction, that a red-blue coloring of \(K_9\) contains neither a red triangle nor a blue \(K_4\). By the Lemma, every vertex has red degree \(3\). The sum of the red degrees is therefore \(9\cdot3=27\).
Let \(m_R\) be the number of red edges. Each red edge contributes \(1\) to the degree of each of its two endpoints, so the sum of the red degrees is \(2m_R\), an even integer. But it was just shown to equal \(27\), which is odd. This contradiction proves that every such coloring contains one of the two monochromatic patterns. \(\square\)
This parity argument is a short application of the handshake lemma: in any finite undirected graph, the sum of the degrees is twice the number of edges. The contradiction depends on forcing the same odd degree, \(3\), at every one of the nine vertices.
Worked Example: Why the Forced Degrees Cannot Occur
Suppose a red-blue coloring of \(K_9\) avoided both patterns. The neighborhood Lemma would assign red degree \(3\) to each vertex. Adding these nine degrees gives
If the red graph had \(m_R\) edges, counting the same endpoint incidences edge by edge would instead give \(\sum_v\deg_R(v)=2m_R\). Thus \(2m_R=27\), or \(m_R=27/2=13.5\). An edge count must be an integer, so the assumed coloring cannot exist.
Check: The contradiction is not that a graph cannot have 27 degree incidences; it is that each edge accounts for exactly two incidences. An odd total cannot be partitioned into pairs.
A Coloring of \(K_8\) Avoiding Both Patterns
To prove the lower bound, it is not enough to say that a suitable coloring exists: we must specify one and check both forbidden patterns. It is convenient to list the red edges. All edges of \(K_8\) not in that list are colored blue.
Worked Example: An Eight-Vertex Coloring with No Forbidden Pattern
Let the vertex set be \(V=\{1,2,3,4,5,6,7,8\}\). Color red the edges
and color every other edge of \(K_8\) blue. The first eight red edges form the cycle \(1,2,3,4,5,6,7,8,1\); the other four are \(15,26,37,48\).
To check for a red triangle, list the red neighbors of each vertex. In the table, the final column records the red edges among that vertex's red neighbors.
| Vertex | Red neighbors | Red edges among those neighbors |
|---|---|---|
| 1 | \(\{2,5,8\}\) | None |
| 2 | \(\{1,3,6\}\) | None |
| 3 | \(\{2,4,7\}\) | None |
| 4 | \(\{3,5,8\}\) | None |
| 5 | \(\{1,4,6\}\) | None |
| 6 | \(\{2,5,7\}\) | None |
| 7 | \(\{3,6,8\}\) | None |
| 8 | \(\{1,4,7\}\) | None |
A red triangle would have some vertex joined in red to the other two, and those other two would also be joined by a red edge. The table shows that this never happens, so there is no red triangle.
For the blue \(K_4\) check, first consider sets with no red edges between their vertices, which are exactly the blue complete subgraphs. The red cycle \(1,2,\ldots,8,1\) alone has no independent set of more than four vertices: between consecutive selected vertices around the cycle there must be at least one unselected vertex. If four vertices are selected, the eight positions must alternate, so the only possible sets are \(\{1,3,5,7\}\) and \(\{2,4,6,8\}\). The red edges \(15\) and \(26\), respectively, belong to these sets. Thus neither alternating set is independent in the full red graph, and there is no red-independent set of size four. Consequently there is no blue \(K_4\).
Check: The red edge count is \(8+4=12\). Each vertex has red degree \(3\), so the degree sum is \(8\cdot3=24=2\cdot12\), independently confirming that count. Since \(K_8\) has \(\binom82=28\) edges, the coloring has \(28-12=16\) blue edges.
Conclusion and a Common Pitfall
The upper-bound proof and the explicit lower-bound coloring settle the value. The proof on nine vertices rules out every coloring avoiding both patterns, while the specified coloring on eight vertices shows that the same guarantee cannot hold one vertex earlier.
Proof. The upper-bound theorem gives \(R(3,4)\le9\). The coloring of \(K_8\) above contains neither a red triangle nor a blue \(K_4\), so \(R(3,4)>8\). Since \(R(3,4)\) is an integer, these inequalities imply \(R(3,4)=9\). \(\square\)
Common pitfall: applying the six-vertex fact to four neighbors. In a hypothetical coloring of \(K_9\), a vertex might have four red neighbors and four blue neighbors. Neither neighborhood has six vertices, so the \(R(3,3)=6\) fact cannot be applied directly to either one. The valid argument uses two distinct observations: the six-vertex fact shows that the blue degree is at most \(5\), while the absence of a red triangle shows that the red degree is at most \(3\). Together they force red degree exactly \(3\), and only then does the parity contradiction apply.
This proof shows why local neighborhood information can yield a global obstruction. Each vertex is constrained by the patterns that could appear among its neighbors; when the constraints force an impossible degree sequence, no coloring with the assumed avoidance properties can exist.
Check Your Understanding
Use the neighborhood bounds and the explicit coloring to test your understanding of the proof.
- Why does a blue triangle inside \(B(v)\) create a blue \(K_4\), and which additional vertex completes it?
- Explain why four red neighbors of a vertex must have all six edges between them blue if there is no red triangle.
- If every vertex of a red graph on nine vertices has degree \(3\), what equation relates its number of edges to its degree sum, and why is that impossible?
- In the \(K_8\) construction, why is it enough to rule out red-independent sets of size four to exclude a blue \(K_4\)?
- Identify the two alternating four-vertex sets in the red 8-cycle and the red edge that disqualifies each one.