ここでは、同じセットの頂点V上に2つの無向グラフが接続されています G1 = [V ; E1] and G2 =[V ; E2]です。また、E1とE2のエッジが異なる色を持つと仮定します。異なるセット内の最小スパニングツリーを見つける
エッジの重みをw（e）とする。e ∈ E1 ∪ E2。
各セットE1とE2に少なくとも1つのエッジを持つスパニングツリーの中で、最小重みスパニングツリー（MSF）を探したいとします。この状態で、これに適切なアルゴリズムを見つけるにはどうすればよいですか？私は一晩中ここで立ち往生した。
は二つのエッジE1 ∈ E1、E2 ∈ E2を考えてみましょう。それらはVの2と4の異なる頂点の間を接続します。 3つまたは4つの頂点を接続する場合、e1が接続する頂点を最初に収縮し（Kruskal's algorithmの各ステップと同じ）、e2の接続頂点を作成し、結果のグラフにminimum spanning tree algorithmを実行するとします。結果は、e1とe2を含むMSTです。
は、あなたがすべてのE1 ∈ E1、E2（まったく同じ2つの頂点を接続しないでください）∈ E2を超えるループ、最軽量の解決策を見つけることによって、総MSTを見つけることができることになります。正しさの証明はKruskal's algorithmのものから簡単に修正することができます。 E1最軽量のエッジまたはE2最軽量のエッジのいずれかが、いくつかのMSTで使用しなければならないので
は実際には、しかし、あなたは、これは、より効率的に行うことができます。 E1、最軽量のエッジがE'1は、使用ないと言う、そしてE'1に同意カットを検討することとします。 MSTには、切断を接続する一部のe ≠ e'1が含まれている必要があります。明らかに、e ∈ E1の場合、eの代わりにe'1を使用することができます。しかし電子∈ E2、および電子が使用できない場合は、電子は、より軽いE'1です。この場合、しかし、E2、E2最軽量エッジがMSTの一部とすることができる収率の引数を繰り返します。したがって、E2、又はE1の任意エッジに沿ってE2で軽量エッジの任意のエッジに沿ってE1の唯一の最も軽いエッジが最初の二つの収縮のために考慮しなければならない
は、上記に言及します。 FがMSTアルゴリズムの複雑さ（F（V、E1 + E2）| | E1 + E2）、
複雑さがΘあります。