Results 1 to 7 of 7

Math Help - contrapositive proof

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    32

    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..
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by mathh18 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2009
    Posts
    32
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by mathh18 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2009
    Posts
    32
    I don't know I'm confused. Does it mean there is one cycle?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by mathh18 View Post
    I don't know I'm confused. Does it mean there is one cycle?
    Yes it does. But how?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jan 2009
    Posts
    32
    That's what I'm confused on
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with a proof - Contrapositive or Contradiction?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 24th 2010, 09:41 AM
  2. Proof by contrapositive
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 14th 2010, 04:45 PM
  3. Simple Contrapositive Proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 19th 2009, 06:03 AM
  4. Contrapositive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 27th 2009, 08:36 AM
  5. Proof by Contrapositive
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 13th 2009, 11:31 PM

Search Tags


/mathhelpforum @mathhelpforum