3
$\begingroup$

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?

1 Answers 1

4

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.

  • 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.2010-09-22