メモ 3.1節 2-連結グラフと部分グラフ 「k-連結」の2通りの見方 グラフを非連結にするのに少なくともk個の頂点を除去する必要がある。 任意の2頂点に対して、それを結ぶ独立な道がk本存在する。 2-連結グラフとその構成

2.3節 道被覆 定理2.3.1 (Gallai & Milgram 1960) 系2.3.2 (Dilworth 1950) 任意の有限な半順序集合(P, ≦)において、Pを被覆する鎖の最小個数は、Pが含む反鎖の要素の最大個数と一致する。

2.2節 一般のグラフにおけるマッチング 定理2.2.3 条件(ii) |T'| + q(C'-T') * (奇数) = |C'| 右辺は偶数だから、 |T'| と q(C'-T') の偶奇は一致する。

2.2節 一般のグラフにおけるマッチング 系2.2.2 (Petersen 1891) 橋をもたない任意の3-正則グラフは1-因子をもつ。 Gに奇数本のS-C辺がある。 ∵ (S-C辺の本数) = 第一項は奇数、第二項は偶数だから、S-C辺の本数は奇数。

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