スパニングツリーとカットは密接に関連していることはすでに見てきました。これが別の接続です。クラスカルのアルゴリズムがスパニングツリーに追加する最後のエッジを削除しましょう。これにより、ツリーが2つのコンポーネントに分割され、グラフにカット（S、S）が定義されます。このカットについて何が言えますか？使用しているグラフが重み付けされておらず、クラスカルのアルゴリズムがそれらを処理するために、そのエッジがランダムに均一に順序付けられていると仮定します。ここに注目すべき事実があります。少なくとも1/n ^ 2の確率で、（S、S）はグラフの最小カットであり、カットのサイズ（S、S）はSとSの間で交差するエッジの数です。これは、プロセスをO（n ^ 2）回繰り返し、見つかった最小カットを出力すると、Gの最小カットが高い確率で生成されることを意味します。重み付けされていない最小カットのO（mn ^ 2 log n）アルゴリズムです。
これは、クラスカルのアルゴリズムを使用してグラフを処理するためのn ^ 2のユニークな方法があるという事実に依存しませんか？つまり、クラスカルのアルゴリズムが10ノードのグラフを処理するための3つの固有の方法しかない場合、この処理をn ^ 2回繰り返しても、n^2の固有の「最後のエッジ」は生成されません。一意の最終カットがn^2未満（つまり、一意の「最後のエッジ」がn ^ 2未満）のシナリオでは、どのように機能しますか？
合計でn^2未満のエッジがある場合はどうなりますか？たとえば、9つのエッジしかない10個のノードの連結グラフを作成できます。つまり、アルゴリズムを何度繰り返しても、n^2個の一意の「最後のエッジ」はありません。この状況でどのように機能しますか？
すべてのエッジをループして、エッジが最小カットであるかどうかを確認する方が簡単ではないでしょうか。nノードのグラフでは、一意のエッジの最大数はn + n-1 + n-2 ... + 1エッジであり、n^2未満です。また、n^2がn^2 log n未満であることを考慮すると、これが高速であるため、すべてのエッジをループするだけではどうでしょうか。