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^\prime$. Now we get spanning tree $T^*+ e - e^\prime.$ Now, let us think what happened when Kruskal ran and produced $T$. It examined all edges in $G$. Including $e$ and $e^\prime$. But, it included only e. So, $w(e)\leq w(e^\prime)$.
Thus $T^*+ e - e^\prime$ 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?