 Solution

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

x

. List vertices in nonincreasing order of their distance from

x

in this tree, breaking ties arbitrarily. The root has distance zero and is last, so

v_{n} = x

Every other vertex has a parent one step closer to the root. That parent is adjacent to it and appears later in the ordering. Hence

\forall i < n \exists j > i : v_{i} v_{j} \in E (H) .

For a graph of one vertex the condition is vacuous and the same ordering works.

 New to topics? Read the docs here!