= Six-vertex monochromatic triangle argument
{title2=$R(3,3)\leq6$}
Choose any <vertex> $v$ of a red-blue colored <complete graph> $K_6$. Its five incident <edges> go to the other five <vertices>. By the <pigeonhole principle>, at least three have the same color. Call their other endpoints $a,b,c$ and, after swapping color names if needed, suppose $va,vb,vc$ are red.
If any of $ab,ac,bc$ is red, it completes a red <triangle in a graph> with $v$. If none is red, all three are blue, so $a,b,c$ themselves form a blue <triangle in a graph>. Both possibilities force a <monochromatic> <triangle in a graph>. This proves the upper bound for the <Ramsey number for triangles> using only five incident <edges> and the three pairs among the selected neighbors; the colors of the other <edges> cannot defeat the argument.
\Image[/ramsey-six-vertex-triangle.png]
{title=The two cases after choosing three red neighbors in a complete graph on six vertices}
Both panels show all 15 <edges> of a <complete graph> on six <vertices>. Faint colored <edges> are example choices outside the decisive argument; bold <edges> exhibit the forced <triangle in a graph>. The selected neighbor color could instead be blue, giving the same argument with the color names exchanged.
Back to article page
