Editing Ramsey's theorem (section)

== Examples ==
=== ''R''(3, 3) = 6 ===
[[File:ramsey theorem visual proof.svg|thumb|2-colour case [[proof without words]].<br /><br />Due to the pigeonhole principle, there are at least 3 edges of the same colour (dashed purple) from an arbitrary vertex ''v''. Calling 3 of the vertices terminating these edges ''x'', ''y'' and ''z'', if the edge ''xy'', ''yz'' or ''zx'' (solid black) had this colour, it would complete the triangle with ''v''. But if not, each must be oppositely coloured, completing triangle ''xyz'' of that colour.]]
[[File:RamseyTheory K5 no mono K3.svg|thumb|upright|A 2-edge-labeling of {{math|''K''{{sub|5}}}} with no monochromatic {{math|''K''{{sub|3}}}}]]

Suppose the edges of a complete graph on 6 vertices are coloured red and blue. Pick a vertex, {{mvar|v}}. There are 5 edges incident to {{mvar|v}} and so (by the [[pigeonhole principle]]) at least 3 of them must be the same colour. [[Without loss of generality]] we can assume at least 3 of these edges, connecting the vertex, {{mvar|v}}, to vertices, {{mvar|r}}, {{mvar|s}} and {{mvar|t}}, are blue. (If not, exchange red and blue in what follows.) If any of the edges, {{math|(''rs'')}}, {{math|(''rt'')}}, {{math|(''st'')}}, are also blue then we have an entirely blue triangle. If not, then those three edges are all red and we have an entirely red triangle. Since this argument works for any colouring, ''any'' {{math|''K''{{sub|6}}}} contains a monochromatic {{math|''K''{{sub|3}}}}, and therefore {{math|''R''(3, 3) ≤ 6}}. The popular version of this is called the [[theorem on friends and strangers]].

An alternative proof works by [[double counting (proof technique)|double counting]]. It goes as follows: Count the number of ordered triples of vertices, {{mvar|x}}, {{mvar|y}}, {{mvar|z}}, such that the edge, {{math|(''xy'')}}, is red and the edge, {{math|(''yz'')}}, is blue. Firstly, any given vertex will be the middle of either {{nowrap|1=0 × 5 = 0}} (all edges from the vertex are the same colour), {{nowrap|1=1 × 4 = 4}} (four are the same colour, one is the other colour), or {{nowrap|1=2 × 3 = 6}} (three are the same colour, two are the other colour) such triples. Therefore, there are at most {{nowrap|1=6 × 6 = 36}} such triples. Secondly, for any non-monochromatic triangle {{math|(''xyz'')}}, there exist precisely two such triples. Therefore, there are at most 18 non-monochromatic triangles. Therefore, at least 2 of the 20 triangles in the {{math|''K''{{sub|6}}}} are monochromatic.

Conversely, it is possible to 2-colour a {{math|''K''{{sub|5}}}} without creating any monochromatic {{math|''K''{{sub|3}}}}, showing that {{math|''R''(3, 3) > 5}}. The unique{{efn|Up to [[Graph automorphism|automorphisms]] of the graph.}} colouring is shown to the right. Thus {{math|1=''R''(3, 3) = 6}}.

The task of proving that {{math|''R''(3, 3) ≤ 6}} was one of the problems of [[William Lowell Putnam Mathematical Competition]] in 1953, as well as in the Hungarian Math Olympiad in 1947.

=== A multicolour example: ''R''(3, 3, 3) = 17 ===
{{multiple image
|image1=K 16 partitioned into three Clebsch graphs.svg
|image2=K 16 partitioned into three Clebsch graphs twisted.svg
|footer=The only two 3-colourings of {{math|''K''{{sub|16}}}} with no monochromatic {{math|''K''{{sub|3}}}}, up to isomorphism and permutation of colors: the untwisted (left) and twisted (right) colorings.
}}

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 {{math|1=''R''(3, 3, 3) = 17}} and {{math|1=''R''(3, 3, 4) = 30}}.<ref name="bananas" />

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 {{mvar|v}}. Consider the set of vertices that have a red edge to the vertex {{mvar|v}}. This is called the red neighbourhood of {{mvar|v}}. The red neighbourhood of {{mvar|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 {{mvar|v}}. Thus, the induced edge colouring on the red neighbourhood of {{mvar|v}} has edges coloured with only two colours, namely green and blue. Since {{math|1=''R''(3, 3) = 6}}, the red neighbourhood of {{mvar|v}} can contain at most 5 vertices. Similarly, the green and blue neighbourhoods of {{mvar|v}} can contain at most 5 vertices each. Since every vertex, except for {{mvar|v}} itself, is in one of the red, green or blue neighbourhoods of {{mvar|v}}, the entire complete graph can have at most {{nowrap|1=1 + 5 + 5 + 5 = 16}} vertices. Thus, we have {{math|''R''(3, 3, 3) ≤ 17}}.

To see that {{math|1=''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 {{math|''K''{{sub|16}}}}, 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.

[[File:Clebsch graph.svg|thumb|right|[[Clebsch graph]]]]

If we select any colour of either the untwisted or twisted colouring on {{math|''K''{{sub|16}}}}, 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 {{math|''K''{{sub|15}}}} that avoid monochromatic triangles, which can be constructed by deleting any vertex from the untwisted and twisted colourings on {{math|''K''{{sub|16}}}}, respectively.

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