Results 1 to 2 of 2

Thread: Bridges

  1. #1
    Senior Member
    Jan 2009


    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
    Aug 2009
    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: Jun 6th 2011, 11:24 PM
  2. Engineering - Bridges?
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: Nov 18th 2009, 02:45 PM
  3. Bridges and Cut-vertices
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Oct 18th 2009, 07:29 AM

Search tags for this page

Search Tags

/mathhelpforum @mathhelpforum