[Math] an Arborescence (Graph Theory)

graph theory

On Wikipedia, it states an arborescence is a digraph for which a vertex $u$ called the root and any other vertex $v$, there is exactly one directed path from $u$ to $v$.

In other words, does that mean an arborescence is a digraph whose underlying graph is a tree?

Best Answer

In fact, more is true. Given any tree, every edge can be given uniquely a direction that is towards the root of the tree. In other words, any tree can be uniquely converted into an arborescence. Conversely, any arborescence can be uniquely converted into a tree by changing each directed edge into an undirected edge.

EDIT: We always assume that there is given a root with the tree or arborescence.

Related Question