Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to prove that if there exists a walk in a graph from $v$ to $w$, then there exists a path in the graph from $v$ to $w$ where $v$ and $w$ are vertices of graph $g$... I am not sure if I answered it the right way.

Let $(V,E)$ represent the graph $g$

Let $v,w$ $\in$ $V$

Let the vertices be $v0,v1,v2$, and

Let the edges be $e0,e1,en$.

I would first shows that this graph has a walk if each vertex is incident to at least one edge. It means that a walk exists between two distinct vertices. From the definition of a path (a walk with no repeated vertices), it can be proven that if there exists a walk, then there exists a path.

i have modified my answer..To prove this i would start by defining what a walk and path are. A walk is an alternating sequence if vertices and edges begining and ending with a vertex where each vertex is incident to both the edge that precedes it and the edge that follows it and where the vertices that both precede and follow it are the end vertices of that edge. A walk is closed if its trivial or both it's first and last vertices are the same.

A path from v to w is a sequence of alternating vertices and edges where each vertex is incident to the edge that precedes it and incident to the edge that follows it.It has no repeated edges and the first and the last vertices are distinct.

from the definition of both walk and path,I can deduce that the path has to be an open walk because the vertices are distinct.

To prove that the walk from v to w is open and therefore a path,it would should not contain no cycle.

Using the theorem which states that a graph which has no isolated or pendant vertices,it has at least one simple circuit/cycle, I would prove that it contains no isolated or pendant vertices. let (V,E) be a graph with no isolated or pendant vertices.The length of any walk in this graph cannot exceed |V|-1 where |V| denotes the number of vertices of the graph ,since a walk of length m passes through m+ 1 distinct vertices.There fore there exists a walk in the graph v,x,...,w in the graph whose length m is greater thatn or equal to the length of every other walk in the graph. Now the final vertex w is incident to only one vertices since the graph contains a pendant vertices(It can not contain an isolated vertices because there would be no connection).This means that there cant be any looping back or cycle between v and w.There fore have proved that there exists an open walk from v to w.

share|cite|improve this question

Your answer isn't very good. First of all, you introduce all kinds of notation, $v,w$, $v_0,v_1,v_2$, $e_0,e_1,e_n$, and then never use them again. Second, proving that there is a walk between two vertices with an edge between them is unnecessary and does not contribute to your proof. Lastly, and most importantly, your proof ends with "from the definition of a path, it can be proven that if there exists a walk, then there exists a path." You can't just state that - that's what you were asked to prove!

My suggestion would be to try proving this by contrapositive.

Assume that there is no path from $v$ to $w$. Suppose you've got a walk starting at $v$. How you gonna get your walk to end at $w$?

Make this rigorous by building up a proof straight from the definitions. If you can't do that, you should go back over the definitions of each, draw out some examples, and make sure you understand exactly what it is you're trying to prove.

share|cite|improve this answer
I am not at all sure that "use the contrapositive" is useful advice in this context. The simplest approach is to show that if there is a $uv$-walk with repeated vertices, we can delete part of the walk and get a shorter $uv$-walk. It follows that a shortest $uv$-walk is a path. – Chris Godsil Dec 24 '12 at 4:17
Sure, either way. The contrapositive refers to an argument that if the set of all paths from $v$ to $w$ is empty then the set of all walks from $v$ to $w$ is empty. You can see both proofs utilize the same concept. – Alexander Gruber Dec 24 '12 at 4:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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