Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-14/2/1/solution
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 14 2 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Every hypergraph independent set in the induced hypergraph is also a hypergraph independent set in . Thus its maximum independent-set size is at most . In any proper hypergraph colouring with at most colours, one colour class would have at least vertices, contradicting that bound. ThereforeThis is the weak hypergraph colouring convention: an hypergraph edge may use two colours, but it may not be monochromatic.
New to topics? Read the docs here!