Past exam of the graph theory course of the University of Oxford / 2011 / 2 / a / i / Solution

Choose a spanning tree of the connected graph and root it at $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. HenceFor a graph of one vertex the condition is vacuous and the same ordering works.