Proving optimality for a new algorithm that finds spanning tree with contradiction

Question

Below is an algorithm that finds a spanning tree:

STNew(G, w)
   Z ← empty array
   for each edge e in E, taken in random order do
       Z ← Z ∪ e
       if Z has a cycle c then
           let e' be a maximum-weight edge on c
           Z ← Z − e'
   return (Z)

Does this algorithm always return a spanning tree?

---

I would say yes. It sort of looks like Kruskals algorithm in disguise - sort-of.

I am trying to prove this using contradiction. See below.

Assume that Z is not a spanning tree. That means there is a cycle or disconnection in the graph. There cannot be a cycle because of Line 4 of the algorithm.

But now, how can I prove that there isn't a disconnection?

Being fairly new to graph theory, I really don't have much of an idea other than that. Would someone have any ideas or advice?

Answer 1

Yes, the algorithm always finds a spanning tree (if such exist, i.e. the graph has a source). Not sure if it finds a minimal spanning tree though. You have already proven there are no cycles in the resulting graph, so we only need to show connectivity.

Proof that the resulting graph is connected:

Assume it is not, and there are (at least) 2 connected components U1,U2.
The original graph is connected, so there is some edge connecting U1, and U2, let it be e. Examine the point where e was chosen and added to Z.
Now, since U1, and U2 are not connected, there is some point that e was removed (otherwise they are connected). Let it be when we iterate some edge e'. The cycle involved contains e (because it is removed), thus it contains a node u1 from U1, and a node u2 from U2, such that e=(u1,u2). W.L.O, let the cycle be u1-v1-v2-...-vk-u2-u1. But note that after removing e, there is still a path u1-v1-v2-...-vk-u2 that connects U1 and U2, so the components are still connected. This remains true for any future iteration, and it means the components U1 and U2 are connected in the resulting graph.
Contradiction.

QED