structural:expansion, linguistic:translation, linguistic:paraphrasing, information:filtering
A multicolour example: R (3, 3, 3) = 17

A multicolour Ramsey number is a Ramsey number using 3 or more colours. There are (up to symmetries) only two non-trivial multicolour Ramsey numbers for which the exact value is known, namely R (3, 3, 3) = 17 and R (3, 3, 4) = 30.

Suppose that we have an edge colouring of a complete graph using 3 colours, red, green and blue. Suppose further that the edge colouring has no monochromatic triangles. Select a vertex v. Consider the set of vertices that have a red edge to the vertex v. This is called the red neighbourhood of v. The red neighbourhood of v cannot contain any red edges, since otherwise there would be a red triangle consisting of the two endpoints of that red edge and the vertex v. Thus, the induced edge colouring on the red neighbourhood of v has edges coloured with only two colours, namely green and blue. Since R (3, 3) = 6, the red neighbourhood of v can contain at most 5 vertices. Similarly, the green and blue neighbourhoods of v can contain at most 5 vertices each. Since every vertex, except for v itself, is in one of the red, green or blue neighbourhoods of v, the entire complete graph can have at most 1 + 5 + 5 + 5 = 16 vertices. Thus, we have R (3, 3, 3) ≤ 17.

To see that R (3, 3, 3) = 17, it suffices to draw an edge colouring on the complete graph on 16 vertices with 3 colours that avoids monochromatic triangles. It turns out that there are exactly two such colourings on K, the so-called untwisted and twisted colourings. Both colourings are shown in the figures to the right, with the untwisted colouring on the left, and the twisted colouring on the right.

If we select any colour of either the untwisted or twisted colouring on K, and consider the graph whose edges are precisely those edges that have the specified colour, we will get the Clebsch graph.

It is known that there are exactly two edge colourings with 3 colours on K that avoid monochromatic triangles, which can be constructed by deleting any vertex from the untwisted and twisted colourings on K, respectively.

It is also known that there are exactly 115 edge colourings with 3 colours on K that avoid monochromatic triangles, provided that we consider edge colourings that differ by a permutation of the colours as being the same.