Question

Show that a directed graph \({\bf{G = }}\left( {{\bf{V,E}}} \right)\) has an arborescence rooted at the vertex r if and only if for every vertex \({\bf{v}} \in {\bf{V}}\), there is a directed path from r to v.

Short answer

Therefore, the given statement is proved as true. That is, a directed graph \(G = \left( {V,E} \right)\) has an arborescence rooted at the vertex r if and only if for every vertex \({\bf{v}} \in {\bf{V}}\), there is a directed path from r to v.

Step-by-step solution

General form

Definition of tree: A tree is a connected undirected graph with no simple circuits.

Definition of Circuit: It is a path that begins and ends in the same vertex.

Arborescence (Definition): Let\({\bf{G = }}\left( {{\bf{V,E}}} \right)\)be a directed graph and let r be a vertex in G. An arborescence of G rooted at r is a subgraph\({\bf{T = }}\left( {{\bf{V,F}}} \right)\)of G such that the underlying undirected graph of T is a spanning tree of the underlying undirected graph of G and for every vertex\({\bf{v}} \in {\bf{V}}\)there is a path from r to v in T (with directions taken into account).

Proof of the given statement

Given that, a directed graph \(G = \left( {V,E} \right)\).

To prove: a directed graph \(G = \left( {V,E} \right)\) has an arborescence rooted at the vertex r if and only if for every vertex \({\bf{v}} \in {\bf{V}}\), there is a directed path from r to v.

Proof:

If there is a directed path from r to all other vertices, then by the definition of arborescence the G has an arborescence rooted at vertex r.

Let G have an arborescence rooted at vertex r. Since, the subgraph T of G contains a path from r to all other vertices, G also has to contain a path from r to all other vertices (more precisely, G contains exactly the same paths, but could also contain shorter paths).

So, there is a directed path from r to v.

Hence proved.