Prove that if there is a walk from u to v then there is also a path from u to v. 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
 A: Hint: 
A walk is an edge sequence. But still can be written down as a sequence of vertices. Suppose there are repeating vertices in this sequence. Say $u$ is such a repeating vertex. Delete all other terms in the sequence till the last occurrence of $u$ in your walk. Do this for all repeating vertices and you will have yourself a path. 
I can't see a way to apply induction to this problem. I'm sorry. Although I don't see why you should.
A: Without induction: $(v_1,\ldots,v_k)$ is a walk from $u$ to $v$ if and only if $(w_1,\ldots,w_k)$ is a walk from $v$ to $u$, where $w_i=v_{k+1-i}$ for every $1\leqslant i\leqslant k$. 
A: 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.
A: @hbm inductive method is also good.
We can also do it using Constructive method:
Our algorithm input = walk (sequence of edges and vertices)
Our algorithm output = path (distinct sequence of edges and vertices) 


*

*pick an element (starting from index 0) and compare with all other elements in string*

*if any repeating element is found, then remove complete sub-array between repetitive elements and also remove one of repetitive element.

*repeat step 3 until last element is picked.


*strings are arrays of characters
