TAOCP 2.3.4.2 Exercise 1

Let $(e_1,\ldots,e_n)$ be an oriented walk from $V$ to $V'$.

taocpmathematicsalgorithmsvolume-1

Section 2.3.4.2: Oriented Trees

Exercise 1. [**] $$M20$$ Prove that if $V$ and $V'$ are vertices of a directed graph and if there is an oriented walk from $V$ to $V'$, then there is a simple oriented path from $V$ to $V'$.

Verified: yes
Solve time: 41s

Let $(e_1,\ldots,e_n)$ be an oriented walk from $V$ to $V'$. Among all oriented walks from $V$ to $V'$, choose one of minimum length, say $(e_1,\ldots,e_m)$. Let

$$ V_0=\operatorname{init}(e_1),\quad V_k=\operatorname{fin}(e_k)\qquad(1\le k\le m), $$

so that $V_0=V$ and $V_m=V'$.

If some vertex occurred twice among $V_0,V_1,\ldots,V_m$, say $V_i=V_j$ with $0\le i<j\le m$, then the portion

$$ (e_{i+1},\ldots,e_j) $$

would be a closed oriented walk from $V_i$ back to $V_i$. Deleting these arcs would leave

$$ (e_1,\ldots,e_i,e_{j+1},\ldots,e_m), $$

which is still an oriented walk from $V$ to $V'$ and has length $m-(j-i)<m$. This contradicts the minimality of $m$.

Hence the vertices $V_0,V_1,\ldots,V_m$ are all distinct. Therefore the initial vertices $\operatorname{init}(e_1),\ldots,\operatorname{init}(e_m)$ are distinct, and the final vertices $\operatorname{fin}(e_1),\ldots,\operatorname{fin}(e_m)$ are distinct. Consequently $(e_1,\ldots,e_m)$ is a simple oriented path from $V$ to $V'$. This completes the proof.

∎