Khác biệt giữa các bản “Cây bao trùm nhỏ nhất”

''Nếu mỗi cạnh có trọng số riêng biệt thì sẽ chỉ có một, và chỉ một cây bao trùm nhỏ nhất.'' Có thể chứng minh phát biểu này bằng [[Quy nạp toán học|quy nạp]] hoặc [[chứng minhPhép phản chứng|phản chứng]]. Điều này đúng trong nhiều trường hợp thực tế, như ví dụ về công ty truyền hình cáp ở trên chẳng hạn, khi đó rất hiếm khi hai con đường lại có ''chính xác'' cùng một chi phí. Phát biểu này cũng được tổng quát hóa cho rừng bao trùm.

Giải thuật đầu tiên để tìm cây bao trùm nhỏ nhất do nhà khoa học người Séc [[Otakar Borůvka]] nghĩ ra vào năm 1926 (xem [[Thuật toán Borůvka|Giải thuật của Borůvka]]). Mục đích của ông là nghĩ ra cách phủ mạng điện hiệu quả tại [[Morava|Moravia]]. Hiện nay có hai giải thuật thường được sử dụng,: [[Thuật toán Prim|Giải thuật của Prim]] và [[Thuật toán Kruskal|Giải thuật của Kruskal]]. Cả ba giải thuật này đều thuộc dạng [[giải thuật tham lam]] chạy với thời gian đa thức, vì vậy bài toán tìm cây bao trùm nhỏ nhất là dạng '''[[FP (độ phức tạp)|FP]]''', và các [[bài toán ra quyết định]] liên quan như xác định xem một cạnh cụ thể có thuộc MST hay không hoặc xác định xem tổng trọng số tối thiểu có vượt quá một giá trị nào đó hay không, là thuộc dạng '''[[P (độ phức tạp)|P]]'''. Một giải thuật tham lam khác không được phổ biến bằng đó là [[giải thuật ngược-xóa]], là dạng đảo ngược của giải thuật của Kruskal.