= Five-cycle Ramsey coloring
{title2=$R(3,3)>5$}
Place five labeled <vertices> around a pentagon. In the <complete graph> $K_5$, color the five perimeter <edges> red and the five diagonals blue. Writing $ij$ for the <unordered pair> $\{i,j\}$, the red pairs are $12,23,34,45,15$, and the blue pairs are $13,14,24,25,35$. This assigns a color to every pair, including every diagonal.
The red <subgraph> is the <cycle graph> $1,2,3,4,5,1$; the blue <subgraph> is the <cycle graph> $1,3,5,2,4,1$. Neither contains a <triangle in a graph>. Consequently, none of the ten triples has all three <edges> red or all three blue, proving the lower bound for the <Ramsey number for triangles>. Crossings in the drawing are not additional <vertices>.
\Image[/ramsey-five-vertex-counterexample.png]
{title=All ten edges of a complete graph on five vertices: red perimeter and blue diagonals avoid monochromatic triangles}
Back to article page
