# Prove : In a connected weighted Graph G, Kruskal's Algorithm constructs a minimum spanning tree

### 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?
-

## 1 Answer

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.

-
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