TAOCP 2.3.4.2 Exercise 5
Assume that $G$ contains an oriented walk $(e_1,\ldots,e_n)$ with $n\ge1$ and \operatorname{fin}(e_n)=\operatorname{init}(e_1).
Section 2.3.4.2: Oriented Trees
Exercise 5. [**] $$M16$$ Let $G$ be a directed graph that contains an oriented walk $(e_1,\ldots,e_n)$ with $\operatorname{fin}(e_n)=\operatorname{init}(e_1)$. Give a proof that $G$ is not an oriented tree, using the terminology defined in this section.
Verified: yes
Solve time: 1m02s
Assume that $G$ contains an oriented walk $(e_1,\ldots,e_n)$ with $n\ge1$ and
$$ \operatorname{fin}(e_n)=\operatorname{init}(e_1). $$
Let
$$ V_0=\operatorname{init}(e_1),\qquad V_k=\operatorname{fin}(e_k)\quad(1\le k\le n). $$
Then $V_n=V_0$, so the walk begins and ends at the same vertex.
If $G$ were an oriented tree with root $R$, the text shows that for each vertex there is a unique oriented path to $R$, and hence there are no oriented cycles. Starting at $V_0$, follow the walk until the first repeated vertex occurs. Since $V_n=V_0$, such a repetition exists. The portion of the walk between the first occurrence and the next occurrence of that vertex is a simple oriented cycle. Therefore $G$ contains an oriented cycle.
An oriented tree contains no oriented cycles, whereas $G$ contains an oriented cycle. Hence $G$ cannot be an oriented tree. This completes the proof.
∎