クラスカル法
したがって、 仮に f の重みが e より小さいとすると、f は e より以前に検討されたはずで、 部分森 Y 3 ⊂ Y ∩ Y 1 {\displaystyle Y_{3}\subset Y\cap Y_{1}} への追加をするか調べたはずである(e は Y 1 {\displaystyle Y_{1}} に含まれない辺の中で Y {\displaystyle Y} に最初に追加された辺であるため、 Y {\displaystyle Y} を形成する過程で e を追加する前の段階の Y {\displaystyle Y} の部分森は Y 1 {\displaystyle Y_{1}} の部分森でもある)。しかし f は Y 1 {\displaystyle Y_{1}} で閉路を形成していないので、 Y 3 {\displaystyle Y_{3}} においても閉路を形成しないはずであり、木に追加されていたはずである。これは、 f が Y {\displaystyle Y} に含まれない辺であるということに反する。よって、f の重みは e より小さいことはない。
以上により、 e と f は同じ重みであることが示される。したがって Y 2 {\displaystyle Y_{2}} も最小全域木である。しかし Y 2 {\displaystyle Y_{2}} は Y 1 {\displaystyle Y_{1}} よりも Y {\displaystyle Y} と共通する辺が1つ多い。これは Y 1 {\displaystyle Y_{1}} の定義と矛盾する。(証明終)