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.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email