Editing Prim's algorithm (section)

== Proof of correctness ==
Let ''P'' be a connected, weighted [[graph theory|graph]].  At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph.  Since  ''P'' is connected, there will always be a path to every vertex.  The output ''Y'' of Prim's algorithm is a [[Tree (graph theory)|tree]], because the edge and vertex added to tree ''Y'' are connected. 

Let ''Y<sub>1</sub>'' be a minimum spanning tree of graph P. If ''Y<sub>1</sub>''=''Y'' then ''Y'' is a minimum spanning tree. Otherwise, let ''e'' be the first edge added during the construction of tree ''Y'' that is not in tree ''Y<sub>1</sub>'', and ''V'' be the set of vertices connected by the edges added before edge ''e''.  Then one endpoint of edge ''e'' is in set ''V'' and the other is not.  Since tree ''Y<sub>1</sub>'' is a spanning tree of graph ''P'', there is a path in tree ''Y<sub>1</sub>'' joining the two endpoints.  As one travels along the path, one must encounter an edge ''f'' joining a vertex in set ''V'' to one that is not in set ''V''.  Now, at the iteration when edge ''e'' was added to tree ''Y'', edge ''f'' could also have been added and it would be added instead of edge ''e'' if its weight was less than ''e'', and since edge ''f'' was not added, we conclude that

:<math>w(f) \ge w(e).</math>

Let tree ''Y<sub>2</sub>'' be the graph obtained by removing edge ''f'' from and adding edge ''e'' to tree ''Y<sub>1</sub>''.  It is easy to show that tree ''Y<sub>2</sub>'' is connected, has the same number of edges as tree ''Y<sub>1</sub>'', and the total weights of its edges is not larger than that of tree ''Y<sub>1</sub>'', therefore it is also a minimum spanning tree of graph ''P'' and it contains edge ''e'' and all the edges added before it during the construction of set ''V''.  Repeat the steps above and we will eventually obtain a minimum spanning tree of graph ''P'' that is identical to tree ''Y''.  This shows ''Y'' is a minimum spanning tree. The minimum spanning tree allows for the first subset of the sub-region to be expanded into a larger subset ''X'', which we assume to be the minimum.