G = (V, E) を完全パッチングをもつグラフとする。

Mp を G = (V, E) の完全マッチングとする。

明らかに、

|Mp| = |V| / 2

が成り立つ。

よって、すべての完全マッチングの辺の数は等しく、その数は、 |V| / 2 である。

Mmax を G = (V, E) の最大マッチングとし、 |Mmax| > |Mp| と仮定して矛盾を導く。

明らかに、

2 * |Mmax| ≦ |V|

が成り立つ。

∴ |Mmax| ≦ |V| / 2 = |Mp|

これは矛盾である。

よって、完全マッチングは最大マッチングである。