Udowodnimy, że dla każdego kroku algorytmu Prima istnieje minimalne drzewo rozpinające zawierające drzewo powstałe w kroku algorytmu.
W kroku pierwszym do drzewa dodawany jest dowolny wierzchołek Ponieważ każde drzewo rozpinające zawiera wszystkie wierzchołki, jako możemy wybrać dowolne minimalne drzewo rozpinające.
Dla dowolnego kroku gdzie wiemy, że graf zawiera się w pewnym minimalnym drzewie rozpinającym W kroku wybierana jest krawędź łącząca wierzchołek należący do grafu z wierzchołkiem nienależącym do grafu Jeżeli krawędź należy do to możemy przyjąć W przeciwnym wypadku, w drzewie musi istnieć inna ścieżka łącząca wierzchołki i Ścieżka taka musi zawierać pewną krawędź łączącą pewien wierzchołęk należący do grafu z pewnym wierzchołkiem do grafu nienależącym. Weźmy wtedy graf powstały przez usunięcie z grafu krawędzi i dodanie krawędzi Krawędź ma wagę mniejszą lub równą wadze krawędzi W przeciwnym wypadku krawędź nie mogłaby być wybrana przez algorytm. Wnioskujemy, że suma wag krawędzi grafu jest nie większa od sumy wag krawędzi grafu Udowodnijmy jeszcze, że graf jest drzewem rozpinającym. Dla dowolnych dwóch wierzchołków istnieje w drzewie ścieżka je łącząca.