EWD771 - 0

About 2-coloured 6-graphs.

Let each of the 15 edges of the complete 6-graph be either red or blue. Three of the 6 nodes are said to form a "homogeneous triangle" if the three edges connecting them are of the same colour. Prove the existence of at least two homogeneous triangles.


We call two edges that meet at a node and are of different colour a "mixed pair" meeting at that node. Because at any node 5 edges meet, at most 2 * 3 = 6 mixed pairs meet at that node. Because we have 6 nodes, there are at most 6 * 6 = 36 mixed pairs. Because each mixed pair occurs in one inhomogeneous triangle and each inhomogeneous triangle contains two mixed pairs, we have at most 36 / 2 = 18 inhomogeneous triangles. The total number of distinct triangles being (6*5*4)/(3*2*1) = 20, we have at least 20 - 18 = 2 homogeneous triangles.

Plataanstraat 5
The Netherlands
29 December 1980
prof.dr. Edsger W. Dijkstra
Burroughs Research Fellow

Transcription by John C Gordon

Last revised on Mon, 30 Jun 2003.