Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Background:

I was studying Theorem 2.3.3 from Introduction to Graph Theory by W. B. West. The main idea of his proof is as follows:
T, resulting tree.
T *, spanning tree of minimum weight.
Let, T $\neq$ T *, then there are edges in T * that are not in T. We first consider only 1 edge. Let's name it e. Hence, T * has all the edges that are in T, except e. Now, if we add e to T *, we should get a cycle, say 'C'. This implies, C has an edge that is not in T. Let's name it e'. Now we get spanning tree T *+ e - e'. Now, let us think what happened when Kruskal ran and produced T. It examined all edges in G. Including e and e'. But, it included only e. So, w(e)$\leq$w(e').

Thus T *+ e - e' is a spanning tree with weight at most T * that agrees with T for a longer initial list of edges than T * does.

  • What does it mean actually?
  • Anybody knows any other proof?
share|improve this question

1 Answer 1

up vote 3 down vote accepted

If T is a tree and one joins two vertices of this tree that are not already joined by an edge with a new edge, one gets a unique circuit C. Now, what happens if one removes an edge from C different from the edge just added to T? One gets a new tree.

share|improve this answer
    
Thanks, but i was pondering on 'longer initial list'. What does that mean? –  user1869 Sep 22 '10 at 15:34
1  
There may be more than one tree that has minimum cost. Two minimum weight trees may agree on on some subset of their edges. –  Joseph Malkevitch Sep 22 '10 at 17:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.