Rooted Tree Corresponds to Arborescence

From ProofWiki
Jump to navigation Jump to search


Let $T = \struct {V, E}$ be a rooted tree with root $r$.

Then there is a unique orientation of $T$ which is an $r$-arborescence.


Recall that a tree is connected and has no cycles.

Thus there is exactly one path from each node of $T$ to each other node of $T$.

Let $A$ be the set of all ordered pairs $x, y \in V$ such that:

$\tuple {x, y} \in E$ and
The unique path from $r$ to $y$ passes through $x$.