瓶頸生成樹
無向圖G的一顆瓶頸生成樹(bottleneck spanning tree)。T是這樣的一顆生成樹，它最大的邊權值在G的所有生成樹中是最小的。瓶頸生成樹的值為T中最大權值邊的權。
即生成樹中最長邊最短的樹。
無向圖的最小生成樹一定是瓶頸生成樹，但瓶頸生成樹不一定是最小生成樹。
命題：無向圖的最小生成樹一定是瓶頸生成樹。
證明：可以采用反證法予以證明。
假設最小生成樹不是瓶頸樹，設最小生成樹T的最大權邊為e，則存在一棵瓶頸樹Tb，其所有的邊的權值小于w(e)。刪除T中的e，形成兩棵數T', T''，用Tb中連接T', T''的邊連接這兩棵樹，得到新的生成樹，其權值小于T，與T是最小生成樹矛盾。[1-2]
命題：瓶頸生成樹不一定是最小生成樹。
?
