Show that this graph is a tree

36 Views Asked by At

Suppose we have a directed multigraph (a graph with loops and parallel edges), with vertex set $V=\{v_1,v_2,\cdots,v_n\}$, such that $d^+(v_i)=d^-(v_i)$ for every $i=1,2,\cdots,n$, i.e. indegree of every vertex is same as its outdegree.

Now let $\mathcal{E}_1$ be the set of all Euler trails that either start or end at the vertex $v_1$ (We could have done this with any other vertex too). Let $S$ be a Euler trail in $\mathcal{E}_1$. For $j\ge2$, denote by $e_j$, the edge through which $S$ leaves the vertex $v_j$ for the last time, never to return to $v_j$.

Consider the graph $T$ with vertex set $V$ and edge set $E=\{e_2,e_3,\cdots,e_n\}$. We need to prove that $T$ is a tree.

Can we assume that $d_{T}^+(v_1)=0$ and $d_T^+(v_j)=1$ for $j\ge2$? Why should it be the case?

1

There are 1 best solutions below

1
On BEST ANSWER

For $k=2,\ldots,n$ the edge $e_k$ has $v_k$ as its source vertex, so $d_T^+(v_k)=1$ for $k=2,\ldots,n$, and $d_T^+(v_1)=0$.

Suppose that $v_\ell$ is the target vertex of $e_k$; then $e_k$ cannot occur later in $S$ than $e_\ell$, since $S$ does not return to $v_\ell$ after leaving it via $e_\ell$. This implies that $T$ is acyclic, since any cycle would have to include a sequence $e_ke_\ell$ with $e_\ell$ preceding $e_k$ in $S$.

Let $k_0\in\{2,\ldots,n\}$; we’ll construct a path starting at $v_{k_0}$. The only edge leaving $v_{k_0}$ is $e_{k_0}$; let $v_{k_1}$ be its target vertex. If $k_1=1$, this path cannot be extended: no edge leaves $v_1$. Otherwise, we can extend the path with $e_{k_1}$, the unique edge leaving $v_{k_1}$; let $v_{k_2}$ be its target vertex. In general, if we have extended the path by an edge $e_{k_i}$ to $v_{k_{i+1}}$, either $k_{i+1}=1$, and the path must terminate here at $v_1$, or we can extend it by $e_{k_{i+1}}$, the unique edge leaving $v_{k_{i+1}}$. Clearly this process must terminate, and it does so at $v_1$ when some $k_i=1$. Thus, from each of the vertices $v_k$ for $k=2,\ldots,n$ there is a unique path in $T$ from $v_k$ to $v_1$, and $T$ is an in-tree rooted at $v_1$.