Algoritme Prim

Misalkan "Y" adalah graf yang diperoleh dengan menghapus "f" dan menambahkan "e" dari "Y". Dapat ditunjukkan bahwa "Y" terhubung, memiliki jumlah cabang yang sama dengan "Y", dan bobotnya tidak lebih besar daripada "Y", karena itu ia adalah pohon rentang minimum dari "P" dan ia mengandung "e" dan semua cabang-cabang yang ditambahkan sebelumnya selama konstruksi "V". Ulangi langkah-langkah di atas dan kita akan mendapatkan sebuah pohon rentang minimum dari "P" yang identis dengan "Y". Hal ini menunjukkan bahwa "Y" adalah pohon rentang minimum.