Problem
COM-B2-M06-P018 The Sharp Bound \(R(3,4)\le9\)
Prove that among any \(9\) people there are either \(3\) pairwise acquainted people or \(4\) pairwise unacquainted people.
Consider the red graph: it has no triangles and no independent set of \(4\) vertices. Estimate degrees.
Translate the problem into an edge-colouring of \(K_9\): red means acquaintance and blue means non-acquaintance. Suppose there is no red triangle and no blue \(K_4\). Consider the red graph \(G\).
The graph \(G\) contains no triangles. Also, it has no independent set of \(4\) vertices, because such a set would correspond to a blue \(K_4\).
We show that every vertex of \(G\) has degree at most \(3\). Indeed, if a vertex \(v\) had \(4\) red neighbours, then there could be no red edges among these neighbours, otherwise a red triangle with \(v\) would appear. Hence these \(4\) neighbours would form an independent set in \(G\), i.e. a blue \(K_4\). Contradiction.
If every vertex had degree exactly \(3\), then the sum of degrees would be \(9\cdot3=27\), impossible because the sum of degrees of a graph is even. Hence there is a vertex \(v\) of degree at most \(2\).
Now consider the vertices not adjacent to \(v\) in the red graph. There are at least \(9-1-2=6\) of them. The red graph induced by these vertices is still triangle-free. By \(R(3,3)=6\), among these \(6\) vertices there is either a red triangle or an independent triple. There is no red triangle, so there is an independent triple.
This independent triple together with \(v\) forms an independent set of \(4\) vertices in the red graph, i.e. a blue \(K_4\). Contradiction. Therefore the required group of people exists.
A strong problem: instead of simple recursion, it uses a graph reformulation through triangles and independent sets.