= Solution
Choose a <spanning tree> of the <connectivity (graph theory)>[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. Hence
$$
\boxed{\forall i<n\ \exists j>i:\ v_iv_j\in E(H).}
$$
For a <graph> of one <vertex> the condition is vacuous and the same ordering works.
Back to article page
