TAOCP 2.3.4.1 Exercise 2
Let $(V_0,V_1,\ldots,V_n)$ be a walk from $V = V_0$ to $V' = V_n$.
Exercise 2. [**] $$M20$$ Prove that if $V$ and $V'$ are vertices of a graph and if there is a walk from $V$ to $V'$, then there is a (simple) path from $V$ to $V'$.
Verified: yes
Solve time: 43s
Let $(V_0,V_1,\ldots,V_n)$ be a walk from $V = V_0$ to $V' = V_n$. If all vertices are distinct, the walk is already a simple path. Otherwise, there exist indices $i < j$ such that $V_i = V_j$. Delete the segment $(V_{i+1},\ldots,V_j)$ from the walk to obtain a new sequence $(V_0,\ldots,V_i,V_{j+1},\ldots,V_n)$. This operation reduces the length of the walk by $j-i$ and preserves the property that consecutive vertices are adjacent.
Repeat this deletion process for each repeated vertex until no repetitions remain. Each deletion removes at least one vertex and therefore the process terminates after at most $n$ deletions. The resulting sequence is a simple path from $V$ to $V'$ because all vertices are distinct and each consecutive pair is adjacent. This completes the proof.
∎