English: Diagram to assist in proof of Prim's algorithm. If ${\displaystyle Y_{1}}$ is a minimum spanning tree, and Y is the tree found by Prim's algorithm, we find e, the first edge added by the algorithm which is in ${\displaystyle Y_{1}}$ but not in Y. Let V be the vertices added to the tree up to that point. Then we find a path in ${\displaystyle Y_{1}}$ between the endpoints of e and find an edge f in that path with one endpoint in V. Then ${\displaystyle Y_{1}-f+e}$ is also a minimum spanning tree, and is in this case equal to Y. In general, more steps may be needed.