Jelaskan Bukti: dari Pohon rentang minimum

Misalkan kebalikannya, yaitu ada dua MST yang berbeda: A dan B.

Karena A dan B berbeda, meski memiliki nodus yang sama, setidaknya ada satu garis yang berada dalam salah satu pohon, tetapi tidak dalam pohon lainnya. Di antara garis-garisnya, misalkan e1 adalah garis dengan bobot terendah; pilihan ini unik karena bobot-bobot garis berbeda satu sama lain. Misalkan e1 berada dalam A.

Karena B adalah MST, {e1}  B harus memiliki siklus C dengan e1.

Sebagai pohon, A tidak memiliki siklus, maka C harus memiliki garis e2 yang tidak ada dalam A.

Karena e1 dipilih sebagai garis unik berbobot minimum di antara garis-garis yang dimiliki oleh tepat salah satu dari A dan B, bobot e2 harus lebih besar daripada bobot e1.

Karena e1 dan e2 adalah bagian dari siklus C, penggantian e2 dengan e1 mengakibatkan pohon rentang dengan bobot yang lebih kecil.

Hal ini menjadi kontradiksi dari pernyataan bahwa B adalah MST.

Secara umum, jika ada garis-garis yang memiliki bobot yang sama, hanya sebagian garis pada pohon rentang minimum yang pasti unik.

Graf bagian dengan bobot minimum

Jika semua bobot adalah positif, pohon rentang minimum adalah graf bagian (subgraf) berbobot minimum yang menghubungkan semua titik. Graf bagian yang memiliki siklus membutuhkan total bobot yang lebih banyak.