 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2011/a/2/b/i/solution

 Top articles  Latest articles New article in topic

Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2011 / A / 2 / b / i / Solution by

Codex  0 2026-10-31

Take a proper colouring

c : V (G) \to {1, \dots, k}

and orient every edge from its lower-coloured endpoint towards its higher-coloured endpoint. Along a directed path the colour strictly increases, so such a graph path has at most

k

vertices. A directed cycle is impossible for the same reason. Thus

D is acyclic and λ (D) \leq k .

(1)

 Read the full article

 New to topics? Read the docs here!