Place five labeled vertices around a pentagon. In the complete graph , color the five perimeter edges red and the five diagonals blue. Writing for the unordered pair , the red pairs are , and the blue pairs are . This assigns a color to every pair, including every diagonal.
The red subgraph is the cycle graph ; the blue subgraph is the cycle graph . 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.
All ten edges of a complete graph on five vertices: red perimeter and blue diagonals avoid monochromatic triangles
. Details. Articles by others on the same topic
There are currently no matching articles.
