The Neighborhood Idea
In a red-blue colouring of a complete graph, every edge receives exactly one of the two colours. To force a monochromatic clique, choose a vertex and divide its neighbors according to the colour of the edge joining them to that vertex. If one group is large enough, the Ramsey property inside that group either supplies a clique of the other colour already or a clique that can be extended by the chosen vertex. The key count is that the two groups partition all the other vertices.
All graphs in this tutorial are finite and simple. A clique is a set of vertices in which every pair is joined by an edge. A red \(K_s\) means a clique on \(s\) vertices whose edges are all red; a blue \(K_t\) is defined in the same way. A two-colouring of \(K_n\) assigns red or blue to each of its edges.
For a vertex \(v\) in a red-blue coloured complete graph, let \(N_R(v)\) be the set of vertices joined to \(v\) by a red edge, and let \(N_B(v)\) be the set joined to \(v\) by a blue edge. Each other vertex is in exactly one of these sets. In particular, if the graph is \(K_n\), then \(|N_R(v)|+|N_B(v)|=n-1\).
The Neighborhood Recurrence
Proof. Set \(a=R(s-1,t)\) and \(b=R(s,t-1)\), and consider any red-blue colouring of \(K_{a+b}\). Choose a vertex \(v\). Its neighborhoods partition the other \(a+b-1\) vertices. Suppose both \(|N_R(v)|<a\) and \(|N_B(v)|<b\). Since these sizes are integers, they would satisfy \(|N_R(v)|\le a-1\) and \(|N_B(v)|\le b-1\), so their sum would be at most \(a+b-2\), contradicting \(|N_R(v)|+|N_B(v)|=a+b-1\). Thus at least one neighborhood reaches its threshold.
If \(|N_R(v)|\ge a=R(s-1,t)\), take any \(a\) vertices in \(N_R(v)\). By the definition of \(R(s-1,t)\), their induced colouring contains either a red \(K_{s-1}\) or a blue \(K_t\). In the first case, every vertex of that clique is joined to \(v\) by a red edge, so adjoining \(v\) gives a red \(K_s\). In the second case, the blue \(K_t\) already has the required size. If instead \(|N_B(v)|\ge b=R(s,t-1)\), take \(b\) vertices in \(N_B(v)\). Their colouring contains either a red \(K_s\), which already suffices, or a blue \(K_{t-1}\). In the latter case all its vertices are joined to \(v\) in blue, so adjoining \(v\) gives a blue \(K_t\). Therefore every colouring of \(K_{a+b}\) has the required monochromatic clique, which proves the stated upper bound. \(\square\)
The two branches are worth distinguishing. A red neighborhood is tested against \(R(s-1,t)\): its red clique needs one more vertex, while its blue clique is already large enough. A blue neighborhood is tested against \(R(s,t-1)\): its blue clique needs one more vertex, while its red clique is already large enough.
Proof. Choose a vertex in a colouring of \(K_{A+B}\). If its red neighborhood has at least \(A\) vertices, apply the first assumed property to \(A\) of them. A red \(K_{s-1}\) extends through the chosen vertex to a red \(K_s\), and a blue \(K_t\) already suffices. Otherwise its red neighborhood has at most \(A-1\) vertices. Since there are \(A+B-1\) neighbors altogether, the blue neighborhood then has at least \(B\) vertices. Apply the second assumed property to \(B\) of them: a red \(K_s\) suffices directly, and a blue \(K_{t-1}\) extends through the chosen vertex to a blue \(K_t\). This proves the claim. \(\square\)
The corollary explains how the recurrence is used when available Ramsey bounds are upper bounds rather than exact values. The proof needs only the two guaranteed properties at sizes \(A\) and \(B\); it does not require knowing the exact Ramsey numbers.
Worked Neighborhood Arguments
Worked Example: A Red Neighborhood Produces the Clique
Let \(G\) be the red-blue colouring of \(K_4\) with vertex set \(V=\{1,2,3,4\}\), red edge set \(E_R=\{12,13,23\}\), and blue edge set \(E_B=\{14,24,34\}\). Decide which monochromatic clique is exhibited by the neighborhood of vertex \(1\), for the target red \(K_3\) or blue \(K_3\).
The six edges of \(K_4\) are \(12,13,14,23,24,34\). The listed red and blue sets are disjoint and together contain all six. At vertex \(1\), the red neighbors are \(N_R(1)=\{2,3\}\), and the blue neighbors are \(N_B(1)=\{4\}\). The edge \(23\) is red, so \(\{2,3\}\) is a red \(K_2\). Both edges from \(1\) to this set, \(12\) and \(13\), are red. Thus \(\{1,2,3\}\) is a red \(K_3\).
Check: the three edges of the claimed clique are \(12,13,23\), and all three appear in \(E_R\). The other neighborhood has only one vertex, so it contains no \(K_2\) that could extend \(1\) to a blue \(K_3\).
Worked Example: A Blue Neighborhood Produces the Clique
Let \(G\) have vertex set \(V=\{1,2,3,4\}\), red edge set \(E_R=\{12,23,24\}\), and blue edge set \(E_B=\{13,14,34\}\). For the target red \(K_3\) or blue \(K_3\), inspect the neighborhoods of vertex \(1\).
Again, \(K_4\) has six edges. The red and blue sets are disjoint and their sizes are \(3\) and \(3\), so they partition all six edges. The red neighborhood is \(N_R(1)=\{2\}\), while the blue neighborhood is \(N_B(1)=\{3,4\}\). The edge \(34\) is blue, and the edges from \(1\) to \(3\) and \(4\), namely \(13\) and \(14\), are also blue. Therefore \(\{1,3,4\}\) is a blue \(K_3\).
Check: the blue edges \(13,14,34\) are exactly the three pairs from \(\{1,3,4\}\). This time it is the blue neighborhood that contains the smaller blue clique and allows it to be extended through \(1\).
Worked Example: A Blue \(K_4\) from a Blue Neighborhood
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\), red edge set \(E_R=\{15,25,35,45\}\), and blue edge set \(E_B=\{12,13,14,23,24,34\}\). Use vertex \(1\) to identify a red \(K_3\) or a blue \(K_4\).
The complete graph \(K_5\) has \(\binom{5}{2}=5\cdot4/2=10\) edges. The red set has \(4\) edges and the blue set has \(6\); they are disjoint and their union is the ten edges of \(K_5\). At \(1\), \(N_R(1)=\varnothing\) and \(N_B(1)=\{2,3,4\}\). The three edges among the blue neighbors are \(23,24,34\), all blue. They form a blue \(K_3\), and the edges \(12,13,14\) from \(1\) to those neighbors are blue as well. Hence \(\{1,2,3,4\}\) is a blue \(K_4\).
Check: the six pairs among \(\{1,2,3,4\}\) are \(12,13,14,23,24,34\), all of which are listed in \(E_B\). The red edges all meet vertex \(5\), so none belongs to this blue clique.
The Off-by-One Pitfall
A common error is to choose a complete graph with one vertex too few. If the neighborhood thresholds are \(a\) and \(b\), the argument needs a vertex with \(a+b-1\) neighbors. A graph \(K_{a+b}\) has exactly that many neighbors at each vertex. In contrast, a graph \(K_{a+b-1}\) has only \(a+b-2\) neighbors at the chosen vertex, which is not enough for the contradiction used in the proof.
For a concrete count, take hypothetical thresholds \(a=5\) and \(b=7\). With \(K_{11}\), a chosen vertex has \(11-1=10\) neighbors. If neither threshold is reached, the red neighborhood can have as many as \(5-1=4\) vertices and the blue neighborhood as many as \(7-1=6\), for a total of \(4+6=10\). There is no contradiction. With \(K_{12}\), the chosen vertex has \(12-1=11\) neighbors, but the same assumption that neither threshold is reached would allow at most \(4+6=10\). Since \(11>10\), at least one threshold must be reached.
The number \(a+b\) in the recurrence is therefore an upper bound obtained by counting the neighbors of a vertex in \(K_{a+b}\). It does not assert that the Ramsey number equals that sum. The neighborhood argument proves only that the required monochromatic clique is guaranteed by that order.
Check Your Understanding
For each question, keep track of which clique is already present inside a neighborhood and which one must be extended through the chosen vertex.
- In the recurrence proof, why does \(|N_R(v)|<a\) imply \(|N_R(v)|\le a-1\)?
- If a red neighborhood contains a blue \(K_t\), why is it unnecessary to use the chosen vertex?
- In a blue neighborhood, which monochromatic clique must be extended to obtain the target blue clique, and what edge colour makes the extension possible?
- For thresholds \(a=6\) and \(b=9\), how many neighbors does a vertex have in \(K_{a+b}\), and what is the largest total allowed if both thresholds are missed?
- Why does proving that every colouring of \(K_{a+b}\) has the target clique establish an upper bound on \(R(s,t)\), rather than an exact value?