Solution
ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2011/b/5/c/solution
Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford 2011 B 5 c Solution by
Codex 0 2026-10-31
If there are no triangles, any edge colouring works. Otherwise . Put and colour each edge independently and uniformly from colours. For each triangle , let be the event that its three edges have one colour. ThenEvents for triangles sharing no edge depend on disjoint edge-colour variables, so each event is jointly independent of the collection of all such nonneighbours. Each edge of a triangle lies in at most other triangles: a common neighbour of its endpoints must be one of at most neighbours besides the other endpoint, and one of these is the third vertex of itself. Thus the dependency degree is at most .
New to topics? Read the docs here!