7
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Ishfaaq Mar 5 '14 at 2:09
  • $\begingroup$ The main difference is that a path doesn't contain a cycle, while a walk could. How can you account for this? $\endgroup$ – Calvin Lin Mar 5 '14 at 2:12
  • $\begingroup$ @Ishfaaq I updated it $\endgroup$ – user126032 Mar 5 '14 at 2:20
  • $\begingroup$ provided u != v $\endgroup$ – Number945 Jan 17 '18 at 16:58
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – bof Mar 5 '14 at 2:41
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What you said is pretty much what induction is! $\endgroup$ – hbm Mar 5 '14 at 2:21
  • $\begingroup$ @hbm: Pardon my idiocy..Don't seem to get it. Would love an explanation.. $\endgroup$ – Ishfaaq Mar 5 '14 at 2:22
  • $\begingroup$ 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. $\endgroup$ – Kelvin Soh Apr 16 '14 at 19:00
0
$\begingroup$

@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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.