You are Here: Home

# Discrete Math

Maths and statistics discussion, revision, exam and homework help.

Announcements Posted on
Find out how cards are replacing warnings on TSR...read more 03-12-2013
1. Discrete Math
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?

2. Re: Discrete Math
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?
3. Re: Discrete Math
(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.
4. Re: Discrete Math
(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.
5. Re: Discrete Math
(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.
6. Re: Discrete Math
(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.
Last edited by ghostwalker; 11-05-2012 at 09:10.
7. Re: Discrete Math
(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.
Last edited by Artus; 11-05-2012 at 10:35.
8. Re: Discrete Math
(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.

## Step 2: Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank

this is what you'll be called on TSR

2. this can't be left blank

never shared and never spammed

3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
1. By completing the slider below you agree to The Student Room's terms & conditions and site rules

2. Slide the button to the right to create your account

You don't slide that way? No problem.

Last updated: May 11, 2012
Study resources