グラフ G = (V, E) が完全マッチングを持つのは、頂点集合 V の任意の部分集合 U に対し、V − U から誘導される部分グラフの、奇数個の頂点を持つ連結成分の個数が高々 |U| 個であるとき、かつそのときに限る タットの定理 - Wikipedia