グラフ理論

2.2節 一般のグラフにおけるマッチング

定理2.2.1 (Tutte 1947)

グラフが1-因子をもつための必要十分条件は、すべてのS⊆V(G)に対して q(G-S) |S| が成り立つことである。

十分性

対偶を考える。

1-因子をもたないならば、q(G-S) > |S| となるS⊆V(G)が存在する。

やり残したこと

• 最後のマッチングのところ