プリム法は最小全域木を求める貪欲アルゴリズムです。
スタートの頂点を一つ決め、それを「現在の木」に加えます。
「現在の木」から伸びている枝の中で、加えても木のままな（＝閉路を作らない）枝でコストが最小な枝を「現在の木」に加えていきます。
そして最終的に「現在の木」が全域木になったらそれが最小全域木になっている…というシンプルなアルゴリズムです。
疑似コードなど詳細なアルゴリズムはWikipediaなどを参照ください。
本題です。背理法で証明します。
最小全域木$T$と、プリム法が出力した全域木$T'$が異なるとします。
プリム法が$T'$を構成していったとき、初めて$T$に含まれない枝を「現在の木」に加えた時点を$Time$とします。$Time$より以前の時刻に加えられた枝は$T$にも$T'$にも含まれていることに注意してください。
時刻$Time$に加えられた枝を$e' = {u, v\}$とします。頂点$u$は時刻$Time$に「現在の木」に含まれいた方の頂点とします。$T'$は木なので、もし$e$を削除すると$u$が含まれる木$T'_u$と$v$が含まれる木$T'_v$に分断されます。
ここで$T$について考えてみます。$T$はやっぱり木なので、「$T'_u$の頂点集合からなる木」と「$T'_v$の頂点集合からなる木」を結ぶ枝$e$が存在します。
ここで$e$と$e'$に着目します。
プリム法は時刻$Time$直前では$T'_u$でした。その状態で$e'$を選んだので、アルゴリズムの動作より$e'$のコストは$e$のコスト以下です。
ここで$T$から$e$を取り除いて$e'$を加えた木$T''$を考えます。
$e' < e$の場合、$T''$は$T$よりコストが小さく全域木になっているので、$T$が最小全域木であることに矛盾します。
$e = e'$の場合、$T$も$T''$も最小全域木です。証明の最初のステップで$T$を$T''$と置き換えて考えることで、$Time$がより遅い議論ができます。どこかで$e' < e$になれば上のパターンで矛盾が導けます。最後まで$e = e'$であれば、$T = T'$になるのでこちらでも$T'$が最小全域木であることが導けます。
最適性の証明で、「最適なもの」と「アルゴリズムが出力したもの」を比較するのはよくある手法です。
$e = e'$のパターンだと最適なものを置き換えていって再起的に証明しているのがエレガントです。