# Prove the correctness of the following greedy algorithm for finding a minimal spanning tree.

I have to prove that the following algorithm finds the minimal spanning tree. Let $$G$$ be the graph were doing the procedure on, and all edges have different weights.

Step 1: Sort the edges in descending order of their weights, meaning : $$c(e_1)>c(e_2)>c(e_3)...>c(e_n)$$.

Step 2: For $$i=1$$ to $$n$$ If $$T-{e_i}$$ is connected, then $$T=T-{e_i}$$

As I understand at first have to prove that after the procedure the result is in fact a tree. This is easy, because we obviously get a connected graph and without a cycle at that (because we erase the reduntant edges), then what we get is a tree.

But how to prove that it is in fact optimal? I tried something along these lines.

Let's assume to the contrary that the tree $$T$$ we get is not optimal, and some other tree $$T'$$ is.

Let's analyze all these edges one by one. In the begining all the edges of $$T'$$ are in $$G$$. We then erase edges from this graph one by one using the algorithm. Let $$e_i$$ be the first edge that's kept in $$G$$ and is not in $$T'$$ or vice versa. Let $$e_i$$ be this element. If $$e_i$$ is this element and it's in $$T'$$ but not $$G$$ then obviously the sum of the first $$i$$ element in descending order in $$T'$$ is bigger than in $$G$$. Now I would like to show, that if $$e_i$$ is in $$G$$ but not in $$T'$$ then we ran into some kind of problem, but I have a problem with that. If we erased $$e_i$$ from $$G$$ then we would disconnect the graph. But would $$T'$$ without $$e_i$$ too be disconnected? It'd be nice if it were obviously, because then my thesis would be proven outright.

Let $i$ be minimal with $T$ and $T'$ disagreeing on $e_i$. So $e_1, \ldots, e_{i-1}$ is in $T$ iff it is in $T'$. Since $T\cup T'$ is connected, the algorithm must have decided to remove $e_i$ from $T$. Hence $e_i$ is in $T'$. Since $T\cup e_i$ has a cycle, pick a cycle of it, which must pass through $e_i$ and hence must contain at least one edge $e_j$ that is not in $T'$. Clearly, $j>i$. Then $T'$ is also minimal for $G-e_j$. On the other hand we may assume by induction on the number of edges in $G$ that the algorithm produces $T'$ when starting with $G-e_j$. That means that at step $i$, removing $e_i$ would cause disconnection. Hence back in the original graph, $T'\cup e_j$ has a cycle that passes through both $e_i$ and $e_j$. Therefore $(T'-e_i)\cup e_j$ is a tree. It has weicght smaller than that of $T'$, contradiction.