Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 14 2 2 Solution Created 2026-10-03 Updated 2026-10-14
If two distinct hypergraph edges survived in and shared two vertices, they were an offending pair in . The deletion set contains a chosen vertex from their union, so at least one of those hypergraph edges could not have survived. This contradiction proves that is a linear hypergraph. Deleting vertices leaves every surviving hypergraph edge of size three, so the construction meets the uniformity requirement as well as the chromatic-number requirement.