# 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

• You need to properly define what you mean by "walk" and "path". As you may know Graph Theory is naturally notorious for its ambiguous definitions. – Ishfaaq Mar 5 '14 at 2:09
• The main difference is that a path doesn't contain a cycle, while a walk could. How can you account for this? – Calvin Lin Mar 5 '14 at 2:12
• @Ishfaaq I updated it – user126032 Mar 5 '14 at 2:20
• provided u != v – Number945 Jan 17 '18 at 16:58

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.

• Or just consider a shortest walk from $u$ to $v$ and show that it must be a path. Of course that is essentially what you did. – bof Mar 5 '14 at 2:41

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$.

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.

• What you said is pretty much what induction is! – hbm Mar 5 '14 at 2:21
• @hbm: Pardon my idiocy..Don't seem to get it. Would love an explanation.. – Ishfaaq Mar 5 '14 at 2:22
• If we want to show more clearly why the process you have described works, we will probably appeal to a reasoning like this: "by removing such a sequence of vertices we arrive at a shorter walk. Eventually we would have removed all repeating vertices until we get a path." This reasoning can be made more formal by induction: by removing such a sequence of vertices we arrive at a shorter walk, which by the induction hypothesis contain a path. – Kelvin Soh Apr 16 '14 at 19:00

@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)

1. pick an element (starting from index 0) and compare with all other elements in string*
2. if any repeating element is found, then remove complete sub-array between repetitive elements and also remove one of repetitive element.
3. repeat step 3 until last element is picked.

*strings are arrays of characters