Question

Suppose that G is a graph and a and b are vertices in G such that a does not =b. Prove that if there is a walk from a to b, then there is a path from a to b.

A walk in the graph is a sequence of vertices where there is an edge between each pair a_i and a_(i+1). The length of a walk is n. If a_0=a_n, ie if the walk begins and ends at the same vertex, then the walk is called a closed walk or a circuit.

A walk from a_0 to a_n is called a trail if no edge is repeated.

A trail is called a path if no edge or vertex(except maybe the first and last) are repeated.

Do not solve the proof but instead give the steps of a procedure that starts with a walk of arbitrary length and results in a path. Indicate why your procedure guarantees you end with a path. You should be able to hand it to someone who needs to get a path!

Answer 1

We prove this by induction on length n of walk.

Step 1] Suppose n=1, then the walk is of length 1 and we know walk of length 1 is also a path and hence the result holds.

Step 2] Now, suppose that the result holds for all the walks of length smaller than n=k.

Step 3] Now we prove the result for the walk of length n=k+1.

Case 1] Suppose the walk has no repeated vertex then, the result holds as we know that a walk with no repeated vertex is a path hence in this case the result holds.

Case 2] Suppose if the walk has a repeated vertex 'x', then suppress the part of walk which lies between the two successive appearance of 'x'. then that will be walk of path less than 'k' and then by step 2 it will have a path from a to b. Which implies the walk of length n=k+1 from a to b has a path from a to b.