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 5671 AL NUENEN The Netherlands |
29 December 1980 prof.dr. Edsger W. Dijkstra Burroughs Research Fellow |
Last revised on