Question

Show that a connected directed graph in which each vertex has the same in-degree and out-degree has a rooted spanning tree. (Hint: Use an Euler circuit.

Short answer

Graph G has a rooted spanning tree.

Step-by-step solution

Compare with the definition.

A spanning tree of a plane graph G is a subgraph of G that is a tree and that carry all vertices of G.

A tree is an undirected graph that is connected and does not contain any single circuit. And a tree with n vertices has \({\bf{n - 1}}\) edges.

An Euler circuit is a simple circuit that contains every edge of the graph.

Show that graph has a rooted spanning tree.

Since G is a connected graph with the same in and out a degree at every vertex, there exists an Euler circuit C in G.

Let us first select a vertex a in C. Follow the circuit C until we arrive at an edge that has a terminal vertex that was already visited in the circuit and remove this edge from the circuit C. Repeat until have checked every edge in the circuit C.

The remaining circuit S is then a rooted tree because there has to be a directed path from the root to every other vertex and there can no longer be a circuit in S.

Moreover, S is also a rooted spanning tree, since S contains all vertices in G.

Therefore, Graph G has a rooted spanning tree.