contrapositive proof

• May 5th 2010, 12:22 PM
mathh18
contrapositive proof
prove that for every connected graph G, if G has no cycles then for every pair of vertices a,b in G, there is only one path from a to b in G.

the contrapositive of this would be easier to prove but i'm not exactly sure how to do that..
• May 5th 2010, 12:30 PM
Plato
Quote:

Originally Posted by mathh18
prove that for every connected graph G, if G has no cycles then for every pair of vertices a,b in G, there is only one path from a to b in G.
the contrapositive of this would be easier to prove but i'm not exactly sure how to do that..

Well what is a cycle?
Is every path from a to b also a path from b to a?
What happens if there are two paths from a to b?
• May 5th 2010, 12:37 PM
mathh18
a cycle is a circuit with the only repeated nodes at the beginning and end.
every path from a to b is also a path from b to a
if there are two paths from a to b, then...there is more than one cycle?
• May 5th 2010, 12:44 PM
Plato
Quote:

Originally Posted by mathh18
if there are two paths from a to b, then...there is more than one cycle?

What? How is that?
How is there at least one cycle?
• May 5th 2010, 12:59 PM
mathh18
I don't know I'm confused. Does it mean there is one cycle?
• May 5th 2010, 01:01 PM
Plato
Quote:

Originally Posted by mathh18
I don't know I'm confused. Does it mean there is one cycle?

Yes it does. But how?
• May 5th 2010, 01:07 PM
mathh18
That's what I'm confused on(Worried)