Let G be a graph and let u and v be two of its vertices. Prove that if there is a walk from u to v then there is also a path from u to v.
Using induction on length of a path, how can I solve this?
walk: A walk in a graph G = (V,E) is a sequence of vertices $v_1$, $v_2$, $v_3$ … $v_k$ s.t. {$v_i$,$v_i$+1} ∈ E for i = 1, …, k-1
path: walk with no repeated vertices or # of edges
Best Answer
We use induction on the length of the walk.
Let $W$ be a walk between $u$ and $v$.
Base step: if $|W| = 1$, then $W$ is just the edge $uv$ and it is a $u-v$ path.
Induction step: Now assume the statement is true for all $u-v$ walks of smaller size than $W$. If all the vertices in $W$ are distinct, then $W$ is $u-v$ path and we are done. Otherwise, $W$ has a repeated vertex say $x$. Let $W'$ be the walk obtained by suppressing the section of $W$ between the two repetition of $x$. Obviously $W'$ is $u-v$ walk of smaller length than $W$. By induction hypothesis, $W'$ has $u-v$ path which means that $W$ has $u-v$ path.