Show that every rooted tree has exactly one source (called the root) and that for every node u of a rooted tree there is exactly one path from the root to u Now assume that G is a finite directed...

Show that every rooted tree has exactly one source (called the root) and that for every node u of a rooted tree there is exactly one path from the root to u

Now assume that G is a finite directed graph with a single sourcer (called the root) and such that for every node u 2 G:V there is exactly one path from r to u in G. Let n = # G :V be the number of nodes in G.

a) Show that every path in G has length at most n.

b) Show that there is a node u in G such that all successors of u are sinks.

c) Show that G is a rooted tree.