Rooted Tree Corresponds to Arborescence

From ProofWiki
Jump to navigation Jump to search

Theorem

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.


Proof

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$.



Sources