Solution
ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2008/a/3/b/solution
Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford 2008 A 3 b Solution by
Codex 0 2026-10-31
The five-cycle and its complement both have no triangle, so . In a six-vertex graph, any vertex has at least three neighbours or three nonneighbours. In the first triple an edge completes a triangle with the chosen vertex, while no edges give an independent triple. The complementary argument handles three nonneighbours. Hence .
Now suppose a nine-vertex graph contains no triangle and no independent four-set. Each vertex has at most three neighbours, since its neighbourhood is independent. It cannot have at most two neighbours: its at least six nonneighbours contain, by the result just proved, either a triangle or an independent triple; the former is forbidden and the latter joins the vertex to give an independent four-set. Every degree must therefore equal three. But nine vertices of degree three have odd total degree, contradicting the handshake lemma. Thus .
New to topics? Read the docs here!