Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/iii/paper-38/4/c/solution

The displayed graph consists of three graph triangles sharing the vertex . In a graph colouring with three colours, every graph triangle uses all three colours. The edge and the edges therefore force to be the two colours different from . Likewise the graph triangle forces to be those same two colours. The third graph triangle imposes no further restriction on these four vertices. Hence
Both two-element sets and their union have cardinality two. This is a Boolean-pair colouring gadget: after fixing a palette graph triangle, the pair encodes opposite truth values.

New to topics? Read the docs here!