[Artus]

Suppose that P_1 and P_2 are two paths from a vertex v to another vertex w in a graph. Prove that the closed walk obtained by following P_1 from v to w and tehn P_2 in reverse from w to v contains a cycle.


My answer: Suppose that there are two paths P_1 and P_2 between v to w. Suppose we go from v to w via P_1. Then from w to v via P_2. By doing this, we will be start from a certain point (v) and end up at the same point (v) through a closed path without repeating any path more than once. This clearly is a cycle.

Answer from the textbook: We think of a path as a sequence of vertices. There are at least two vertices of P_2 that are also in P_1 (v and w, for example). Let u not equal to w be the first vertex of P_1 that is encountered on the reversed path P_2 from w back to v. (It is possible that u might equal v.) It follows that the path from u to w along P_1 followed by the path back to u along P_2 in reverse from w is a cycle.

My question: Do you think my answer is correct? If not, can you please explain why? Also, why did the textbook need to introduce another vertex u?

Thanks in advance

[ghostwalker]

At no point does it say that the two paths from v to w are disjoint; they may share edges in common. As such going all the way from v to w and back may use the same edge twice.

I have to say I don't think much of their answer either. What book is this from?

[Artus]

(Original post by ghostwalker)
At no point does it say that the two paths from v to w are disjoint; they may share edges in common. As such going all the way from v to w and back may use the same edge twice.

I have to say I don't think much of their answer either. What book is this from?

So do you think my answer is correct? Or is it missing something?

The textbook is "Discrete Mathematics with Graph Theory" by Edgar G. Goodaire and Michael M. Parmenter.

[ghostwalker]

(Original post by Artus)
So do you think my answer is correct? Or is it missing something?

Since the two paths from v to w could share an edge in common, this contradicts your statement that they have no edge in common. So your answer can't be correct.

The textbook is "Discrete Mathematics with Graph Theory" by Edgar G. Goodaire and Michael M. Parmenter.

If your previous thread related to this book as well, I shall definitely put it on my list of books not to buy.

[Artus]

(Original post by ghostwalker)
Since the two paths from v to w could share an edge in common, this contradicts your statement that they have no edge in common. So your answer can't be correct.



If your previous thread related to this book as well, I shall definitely put it on my list of books not to buy.

I'm sorry, I think I forgot to tell you...the topic for this section is "Trees", so you cannot use the same edge twice.

[ghostwalker]

(Original post by Artus)
I'm sorry, I think I forgot to tell you...the topic for this section is "Trees", so you cannot use the same edge twice.

If this graph is a tree, then there is only one path from v to w. This question makes even less sense now.

[Artus]

(Original post by ghostwalker)
If this graph is a tree, then there is only one path from v to w. This question makes even less sense now.

I didn't say it was a tree, but this question is in the "Trees" section. So probably, the question is trying to show us that if there are two different paths between v and w then it will have a cycle and it is not a tree. So, probably, they want to show us a property of trees (that it doesn't have a cycle). Basically, they are trying to teach us that, if we are trying to determine whether or not a graph is a tree (in the future), we will know that it is not if there are two paths between any two points.

[ghostwalker]

(Original post by Artus)
...

If we make the assumtion that the two paths are distinct (have no edges in common), then they could still have vertices in common. E.g. like a figure of eight, in its simplest form.

Would that be considered a cycle under your definitions? If not, then that's where your proof falls down.