Results 1 to 2 of 2

Math Help - Minimum Cost Spanning Tree

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    30

    Minimum Cost Spanning Tree

    If a loopless weighted graph (G,W) has a unique edge  e_{m} of minimum weight-- that is,  W(e_{m}) < W(e) for  e \neq e_{m} -- show that any minimum cost spanning tree of G must contain  e_{m} .

    I realize this is true, but I need to prove it. I used Kruskal's Algorithm to show that there is at least one minimal cost spanning tree that includes  e_{m} . I'm just stuck trying to think of how to prove that edge is in ANY minimal cost spanning tree.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    I think that you can do it by contradiction.

    Suppose that there is a minimum cost spanning tree that does not contain e_m. Then, adding e_m to the tree forms a cycle. But if you drop one of the other edges in the cycle, the graph stays connected and is cycle-free (i.e. it is a tree) but has a lower cost than before. This contradicts the minimality of cost. Therefore, any minimum cost spanning tree must contain the edge e_m.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Spanning Tree's in the Complete Bipartite Graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 26th 2011, 04:33 AM
  2. Replies: 0
    Last Post: February 20th 2011, 05:03 AM
  3. minimum spanning tree
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 21st 2010, 09:21 AM
  4. minimum spanning tree/shortest route problem
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: January 7th 2010, 03:30 AM
  5. Spanning tree question.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 7th 2007, 07:01 PM

Search Tags


/mathhelpforum @mathhelpforum