Question

Proposition: If a graph is connected by walks, then it is also connected by paths. That is, suppose any two vertices x,y ∈ V can be connected by a sequence of neighboring vertices, a walk W = v(0)v(1)...v(k) where each step is along an edge, v(i)v(i+1) ∈ E for all i, and v(0) = x , v(k) = y. In W, we may come back to the same vertex several times, but the Proposition says we can cut W down to a path P of neighboring vertices with no repeats, P = v(0)v(i1)v(i2)...v(k) which skips from vertex 0 to vertex i1 to vertex i2, etc., before finishing at v(k) = y, but each step is still along an edge.

Answer 1

Problem: Give an algorithm, a clear sequence of steps like a computer program, which takes the vertex sequence W as input and gives the corresponding vertex sequence P as output.

Answer 2

try adding a figure ... a picture's worth million words

Answer 3

I do not have one, that is exactly how the problem is presented to me.

Answer 4

Draw a picture from the information given.

Answer 5

yep ... that will help to communicate as well as ... you will have better grasp of your problems