Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/iii/paper-38/4/c/solution
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 4 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
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. HenceBoth 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!