This is an algorithm for finding a minimum spanning tree in a connected UN-directed graph G=(V,E):
Initialization: B = ∅ - The group of edges that will be built by the algorithm
while |B| < |V| - 1 do:
a. choose some cut in the graph (S,V\S) which there isn't an edge e belongs to B that cross it.
b. find the lightest edge crossing that cut.
c. add it to the group B.
B = B ∪ {e}.
return T = (V,B)
The meaning of cut is described in the attached image: Cut's meaning the vertices s,u are in one group we can call S.
all the other vertices are in the group V\S.
so this is the meaning of (S,V\S) as a cut.
also - the edge (u,w) is a crossing edge
(u,v) is the lightest crossing edge in that specific cut.
(s,u) is not a "crossing" edge
I need to prove that the algorithm will stop eventually. That |B| = |V| - 1 at some point.
I can use the following say in the proof:
'In any point of the algorithm, there exist a minimum spanning tree T=(V,Et) of G that contains the group of edges B that were chosen by the algorithm.'
assuming I already proved that, I need to somehow show that there's is always some cut in the graph that none of his crossing edges been added to B yet. while |B|<|V|-1 . but I'm not sure how to do that
Let us assume that there is no such cut and |B| < |V| - 1. As the tree is connected, this means that all the vertices are connected by some edge in B (Because if a vertex is not connected, there will be a cut in which no edge belongs to B separating that vertex and the spanning tree)
As, |V| vertices need at least |V| - 1 edges to be connected, we infer that |B| >= |V| - 1, thus contradicting our assumption.
Hence Proved.
