2.2節 一般のグラフにおけるマッチング 定理2.2.1 (Tutte 1947) グラフが1-因子をもつための必要十分条件は、すべてのS⊆V(G)に対して q(G-S) |S| が成り立つことである。 十分性 対偶を考える。 1-因子をもたないならば、q(G-S) > |S| となるS⊆V(G)が存在す…