Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-14/2/1/solution

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. Therefore
This 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!