0714132人目の素数さん
2018/11/13(火) 16:04:57.98ID:hCijuWIVMp を G = (V, E) の完全マッチングとする。
明らかに、
|Mp| = |V| / 2
が成り立つ。
よって、すべての完全マッチングの辺の数は等しく、その数は、 |V| / 2 である。
Mmax を G = (V, E) の最大マッチングとし、 |Mmax| > |Mp| と仮定して矛盾を導く。
明らかに、
2 * |Mmax| ≦ |V|
が成り立つ。
∴ |Mmax| ≦ |V| / 2 = |Mp|
これは矛盾である。
よって、完全マッチングは最大マッチングである。