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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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|cite|improve this question
up vote 4 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|cite|improve this answer
Thanks, but i was pondering on 'longer initial list'. What does that mean? – user1869 Sep 22 '10 at 15:34
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


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