この問題を解くのに重要な補題として次がありますが、解説スライドではまともに証明されていません。

• 2次元平面上の2N個の異なる点\((x_1, y_1), (x_2, y_2), \cdots, (x_{2N}, y_{2N})\)が与えられる。
• 2N頂点のグラフを考え、\(x_i = x_j\)か\(y_i = y_j\)を満たす、またそのときのみ辺\((i, j)\)を張る。
• この時、グラフが連結ならば必ずこのグラフは完全マッチングを持つ。

この補題を数学的帰納法で証明します。\(N=1\)ならば明らかなので\(N \geq 2\)とします。

グラフが連結ならば全域木が取れます。頂点数が\(2N \geq 4\)であることから、全域木の高さが \(2\) 以上となるように根を選ぶことができ、この時に最も高さの高い頂点(のうち一つを) \(u\) とします。\(u\) は明らかに葉であり、\(u\)の親を \(p\) 、\(u\) の親の親を \(q\) とします

• \(p\) の次数が \(2\), つまり \(u\) のみを子として持つ場合: マッチング \((u, p)\) を取れば \(N\) が一つ小さい場合に帰着されます
• \(p\) の次数が \(3\) 以上、つまり \(u\) 以外の子を持つ場合: \(u\) 以外の子を一つ選び、\(v\) とします。 \(u\) の選び方から \(v\) も葉であることに注意します。辺の張り方から、 \((u, v), (u, q), (v, q)\) のうち少なくとも一つは辺が存在します。
  • 辺 \((u, v)\) が存在する場合: マッチング \((u, v)\) を取ればいいです。
  • 辺 \((u, q)\) が存在する場合: マッチング \((v, p)\) を取ればいいです。
  • 辺 \((v, q)\) が存在する場合: マッチング \((u, p)\) を取ればいいです。