Rooted Tree Corresponds to Arborescence

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

This article, or a section of it, needs explaining. In particular: This is in fact a result that already exists and can be quoted directly. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

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

This needs considerable tedious hard slog to complete it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Finish}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Sources

• 1968: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms: $\S 2.3.4.2$