設 $e=(u,v)$ 是 $G$ 中權重最小的邊。$G$ 連通，所以最小生成樹存在，任取一棵最小生成樹 $T$。

若 $e\in T$，證明完成。

若 $e\notin T$：把 $e$ 加進 $T$，$T+e$ 恰好有一個迴圈 $C$，而且 $C$ 經過 $e$。$C$ 上除了 $e$ 還有別的邊，任取一條 $e'\ne e$。令 $T'=T+e-e'$ 拿掉迴圈上的一條邊不會破壞連通，$T'$ 仍有 $|V|-1$ 條邊且連通，所以是生成樹。因為 $e$ 是全圖權重最小的邊，$w(e)\le w(e')$，於是 $w(T')=w(T)+w(e)-w(e')\le w(T)$ $T$ 是最小生成樹，所以 $w(T')=w(T)$，$T'$ 也是最小生成樹，而且包含 $e$。

所以 $(u,v)$ 一定屬於某一棵最小生成樹（權重相同的邊有好幾條時，不一定屬於每一棵）。