#6 Ramsey-Type Ideas

If there are at most \(2\) red edges and at most \(2\) blue edges, then there are at most \(4\) edges in total. But there are \(5\). Hence at least one colour appears at least \(3\) times.

A triangle has \(3\) edges and only \(2\) colours. By the pigeonhole principle, two edges have the same colour.

Choose a vertex \(v\). From it, \(3\) edges leave in two colours. By the pigeonhole principle, two of them have the same colour, say \(va\) and \(vb\).

Then \(a-v-b\) is a path of two edges of one colour.

Place the vertices as a pentagon. Colour the five sides red and the five diagonals blue.

The red graph is a cycle of length \(5\), so there is no red triangle. The blue graph is also a cycle of length \(5\), so there is no blue triangle.

If there are at most \(m-1\) red edges and at most \(m-1\) blue edges, then there are at most \(2m-2\) edges in total. But there are \(2m-1\) edges. Hence one colour appears at least \(m\) times.

Choose a vertex \(v\). From it, \(5\) edges leave, so at least \(3\) have the same colour. Let these be red edges to vertices \(a,b,c\).

If at least one of the edges \(ab,bc,ca\) is red, it forms a red triangle with \(v\). If none of these edges is red, then all of them are blue, and vertices \(a,b,c\) form a blue triangle.

Build a graph on \(6\) vertices: the vertices are people. Colour an edge red if the two people are acquainted, and blue if they are not.

By the \(K_6\) result, this colouring contains a monochromatic triangle. A red triangle means \(3\) pairwise acquainted people, and a blue triangle means \(3\) pairwise unacquainted people.

The \(K_6\) result shows that with \(6\) vertices a monochromatic triangle is unavoidable, so \(R(3,3)\le6\).

On the other hand, colour \(K_5\) as follows: the sides of a pentagon are red and the diagonals are blue. Each colour forms a cycle of length \(5\), so there is no monochromatic triangle. Hence \(R(3,3)>5\).

Therefore \(R(3,3)=6\).

Take a vertex \(v\). If three red edges leave it to \(a,b,c\), then no edge among \(a,b,c\) can be red, otherwise there is a red triangle with \(v\). Hence all edges among \(a,b,c\) are blue, giving a blue triangle. Contradiction.

Thus the red degree of every vertex is at most \(2\). Similarly, the blue degree is at most \(2\). But \(n-1\) edges leave a vertex, so \(n-1\le4\), hence \(n\le5\).

From any vertex, \(2m-1\) edges leave. By the strengthened pigeonhole principle, among these edges there are at least \(m\) edges of one colour. Thus any vertex works.

First show that \(t\) vertices are enough. In a red-blue colouring of \(K_t\), if there is a red edge, then there is a red \(K_2\). If there are no red edges, then all edges are blue, and all \(t\) vertices form a blue \(K_t\).

Fewer than \(t\) vertices are not enough: colour all edges blue. Then there is no red \(K_2\), and there is no blue \(K_t\) because there are fewer than \(t\) vertices. Hence \(R(2,t)=t\).

Among any chosen \(6\) of the \(7\) people, by \(R(3,3)=6\), there are already either \(3\) pairwise acquainted people or \(3\) pairwise unacquainted people. Hence such a triple also exists among all \(7\) people.

The number \(7\) is not the exact threshold because the same result is already guaranteed for \(6\) people.

Let \(N=R(s-1,t)+R(s,t-1)\), and colour the edges of \(K_N\) red and blue. Choose a vertex \(v\). The remaining \(N-1\) vertices split into red neighbours and blue neighbours of \(v\).

If there are at least \(R(s-1,t)\) red neighbours, then inside them there is either a red \(K_{s-1}\) or a blue \(K_t\). In the first case, together with \(v\) we get a red \(K_s\); in the second case, we already have a blue \(K_t\).

If there are fewer than \(R(s-1,t)\) red neighbours, then there are at least \(R(s,t-1)\) blue neighbours. Inside them there is either a red \(K_s\), or a blue \(K_{t-1}\), which together with \(v\) gives a blue \(K_t\).

In all cases, the required structure exists.

By Ramsey recursion,

\[R(3,4)\le R(2,4)+R(3,3).\]

Using \(R(2,4)=4\) and \(R(3,3)=6\), we get \(R(3,4)\le10\). Thus every red-blue colouring of the edges of \(K_{10}\) contains either a red \(K_3\) or a blue \(K_4\).

Translate this into people: red edge means acquaintance, blue edge means non-acquaintance. We get either \(3\) pairwise acquainted people or \(4\) pairwise unacquainted people.

By Ramsey recursion,

\[R(4,4)\le R(3,4)+R(4,3).\]

By symmetry, \(R(4,3)=R(3,4)\). Since \(R(3,4)\le10\), we obtain

\[R(4,4)\le10+10=20.\]

Colour the edge between two people red if they are acquainted, and blue if they are not. By the bound \(R(4,4)\le20\), in \(K_{20}\) there is either a red \(K_4\) or a blue \(K_4\).

A red \(K_4\) means \(4\) pairwise acquainted people, and a blue \(K_4\) means \(4\) pairwise unacquainted people.

If the red graph is connected, we are done. Suppose it is not connected. Then its vertices split into several red components.

Any edge between two different red components cannot be red; otherwise those components would merge. Hence all such edges are blue.

We show that the blue graph is connected. If two vertices lie in different red components, they are joined by a blue edge. If they lie in the same red component, take a vertex from another red component; both edges to it are blue, so there is a blue path of length \(2\). Therefore the blue graph is connected.

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.

Choose a vertex \(v\). From it, \(16\) edges leave in three colours, so by the pigeonhole principle at least \(6\) of them have one colour. Let these be red edges to a set \(A\) of \(6\) vertices.

If there is a red edge inside \(A\), it forms a red triangle together with \(v\). If there are no red edges inside \(A\), then all edges inside \(A\) are coloured with the two remaining colours.

By \(R(3,3)=6\), every two-colouring of the edges on \(6\) vertices contains a monochromatic triangle. It is monochromatic in one of the two remaining colours. Hence the original three-colouring also contains a monochromatic triangle.

We first prove that either the red or the blue graph is connected. If the red graph is connected, then it has a spanning tree, and that tree is red.

Suppose the red graph is not connected. Then its vertices split into red components. Any edge between different red components is blue; otherwise those components would be one component. Therefore the blue graph is connected: vertices in different red components are joined by blue edges, and two vertices inside the same red component are connected by a blue path of length \(2\) through a vertex from another component.

Thus the blue graph is connected, and every connected graph has a spanning tree. This tree is blue and passes through all vertices.