How to prove that the algorithm solution is optimal?

The Prim algorithm is to find the minimum generating tree of a graph, that is, a tree with the least possible weight of its edges. Source: Wikipedia

It begins with any arbitrary node of the graph and places it on tree A. At each subsequent step it inserts the lesser edge that has exactly one vertex inside tree A and another outside A, repeating until all of us are added

The easiest way to prove it is by contradiction . But for this you have to use the cycle property : "For any cycle C of the graph, if the weight of one edge [e] of the cycle is greater than of all other edges of the cycle, then [e] does not belong to the minimum generating tree ".

Assume that edge [e] belongs to the minimum generating tree T;

Show that there is another lower-cost T 'generating tree that does not use [e];

Conclude that edge [e] can not belong to the minimum generating tree T (contradiction).

Another way to prove it is by induction . The hypothesis is that at each iteration of the algorithm, tree A is a subgraph of the minimum generating tree T.

This is trivial in the first step, since tree A has only one node and no edge, and obviously this node must be in T.

Now suppose that in some step we have A (T subgraph) and the Prim algorithm says to include the edge [e]. We need to prove that AU [e] is also a subtree of some T. If [e] belongs to T then this is true, since by induction A is a subtree of T and [e] belongs to T, then AU [e] is a subtree of T.

Now suppose that [e] does not belong to T. Consider what happens when we add [e] to T. This creates a cycle. Since [e] has a vertex in A and a vertex outside A (because the algorithm added), there must be an edge [e '] in this cycle that has exactly one vertex in A. The algorithm could have added [e'] , but solved insert [e], which means that the weight (e)