Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2014/6/b/iii/solution

Fix . It has five incident edges, so three of them have the same color by the pigeonhole principle. Suppose they are red, with other endpoints . Any existing edge among must be blue, or it would complete a red triangle with .
If all three edges among existed, they would therefore form a blue triangle. Thus their triple must contain the unique missing edge . In particular, both and belong to the three red neighbors, so and are both red. The identical argument works if the chosen three edges are blue.
Therefore and have the same color for every . The missing edge is crucial: it is the only way the monochromatic neighbor triangle can fail to be present.

New to topics? Read the docs here!