Ordering of vertices
Task number: 4213
Show that for each tree with \( n \) vertices there is an order of vertices \( \{v_1,…, v_n \} \) such that for every \( i > 1 \) it holds that \( v_i \) has exactly one neighbor in the set \( \{v_1,…, v_ {i-1} \} \).
Hint
Remove vertices so that every has only one ancestor.
Solution
If the tree has two vertices, then every ordering is good.
If it has more vertices, it has at least one vertex that is not a leaf, so we root the tree in this vertex. Now we gradually remove the root and declare each of its neighbors as the root (we work with the forest). Each root at a given moment has exactly one neighbor between the already numbered vertices.
