Results 1 to 2 of 2

Math Help - Bridges

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Bridges

    Let G be a connected graph and e1 and e2 be two edges of G. Prove that G-e1-e2 has three components iff both e1 and e1 are bridges.

    I think I know how to prove it one way...if both e1 and e2 are bridges, then G-e1 is disconnected and the same for G-e2....So G-e1 produces two components, and G-e2 produces a third component..

    I don't know how to prove in the other direction though.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    by contradiction: if one of e1, e2 were not a bridge, then its deletion would not increase the number of connected components, i.e. wlog G-e1 is connected. By subsequent deletion of e2 the number of connected components is at most 2, a contradiction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. creating a matrix for the game bridges
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: June 6th 2011, 11:24 PM
  2. Engineering - Bridges?
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 18th 2009, 02:45 PM
  3. Bridges and Cut-vertices
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2009, 07:29 AM

Search Tags


/mathhelpforum @mathhelpforum