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?