グラフ、次数、道

次数を合計するとき、各辺はちょうど二回数えられる——両端の頂点からそれぞれ一回ずつである。したがって合計は偶数になる。次数が偶数の頂点はすでに偶数分を合計に寄与しているので、次数が奇数の頂点の個数も偶数でなければならない。

任意の有限グラフ $G = (V, E)$ を考える。頂点 $v$ が辺 $e$ の端点であるようなすべての頂点-辺接続ペア $(v, e)$ からなる集合を作り、これを2通りの方法で数える。頂点ごとに数えると:各頂点 $v$ はちょうど $\deg(v)$ 個の接続ペアを寄与する(それに触れる辺ごとに1つ)ので、合計は $\sum_{v \in V} \deg(v)$ となる。辺ごとに数えると:各辺 $e = \{u, w\}$ はちょうど $2$ つの端点 $u$ と $w$ を持つので、ちょうど $2$ 個の接続ペアを寄与し、すべての $|E|$ 本の辺について合計すると $2|E|$ となる。

両方の数え方は同じペアの集合を数えているので、一致しなければならない:$\sum_{v \in V} \deg(v) = 2|E|$。第二の主張については、和を偶数次数の頂点と奇数次数の頂点に分ける:$\sum_{v \text{ even}} \deg(v)$ は偶数の和であるから偶数であり、したがって $\sum_{v \text{ odd}} \deg(v)$ も偶数でなければならない(全体の和 $2|E|$ が偶数だから)。奇数の和が偶数になるのは項の個数が偶数のときに限られるので、奇数次数の頂点の個数 $O$ は偶数である。

任意の道をたどるとき、(始点・終点以外の)頂点を通過するたびにその頂点の辺を二本使い切るので、行き詰まる可能性のある頂点(両端点を除く)は次数が偶数でなければならない——これが易しい方向である。逆(偶数次数で十分であること)は帰納的な議論で示される:閉じた小さな道を取り出してつなぎ合わせる(ヒアホルツァーの構成、1873年)。

(必要性。) 連結グラフ $G$ がオイラー閉路 $C$——すべての辺をちょうど一度使う閉じた道——を持つとする。$C$ が始点・終点以外の頂点 $v$ を通過するたびに、1本の辺から入り、別のまだ使われていない辺から出るので、$v$ に接続する辺をちょうど $2$ 本消費する。$C$ は完了時までに $v$ のすべての辺をちょうど一度使うので、始点・終点(最初に出発する辺が最後に到着する辺と対になる)を含むすべての頂点で $\deg(v)$ は偶数でなければならない。

(十分性。) 逆に、連結グラフ $G$ のすべての頂点が偶数次数であるとする。任意の頂点から出発し、未使用の辺に沿って貪欲に歩く。すべての頂点が偶数次数なので、道が始点以外の頂点に入るたびに必ずまた出ることができ(偶数本の接続辺がちょうど $1$ 本の未使用辺にまで減ることはあり得ない)、道は始点に戻る場合を除いて行き詰まることがなく、閉じた道 $C$ が得られる。$C$ がすでにすべての辺を使っていれば終了である。そうでなければ、$G$ は連結なので、$C$ 上のある頂点 $v$ に未使用の接続辺がある。未使用の辺もまたすべての頂点で偶数次数を保つ(偶数次数の閉路 $C$ を取り除いても偶奇は保たれる)ので、同じ議論により、それらは $v$ を通るもう一つの閉じた道 $C'$ を構成する。$C'$ を $v$ で $C$ に継ぎ足すとより長い閉じた道ができる。この継ぎ足し操作(ヒアホルツァーの構成、1873年)を未使用の辺がなくなるまで繰り返すと、オイラー閉路が得られる。

ある $S$ について $|N(S)| < |S|$ であれば、$S$ の頂点を単射的にマッチさせるには近傍が足りないので、この条件が必要であることは明らかである。この条件が十分でもあることは、マッチングがまだ完全でないときに常に増加道を見つけられることによって証明される(ケーニッヒ–エゲルヴァリの増加道の議論)。

(必要性。) ある $S \subseteq X$ が $|N(S)| < |S|$ を満たすとすると、$S$ の頂点は $Y$ 全体を合わせても $|S|$ 未満のパートナー候補しか持たないので、$S$ を $Y$ へ単射的にマッチさせるマッチングは存在し得ない——したがって $X$ 全体を覆うマッチングも存在し得ない。よってホールの条件 $|N(S)| \ge |S|$ は明らかに必要である。

(十分性。) ホールの条件は成り立つが、あるマッチング $M$ で頂点 $x_0 \in X$ がマッチされていないとする。$x_0$ から交互木を構築する:$X$ の頂点からは非マッチング辺を、$Y$ の頂点からはマッチング辺をたどり、こうして到達できるすべての頂点を探索する。この木が $M$ に覆われていない $Y$ の頂点 $y$ に到達したら、$x_0$ から $y$ への道は非マッチング辺・マッチング辺を交互にたどり奇数の長さを持つので、その道に沿ってマッチ済みと未マッチの辺を入れ替える(対称差 $M \triangle P$ を取る)とマッチングのサイズが厳密に1増え、この枝に沿って $M$ がすでに最大であったことに矛盾する——未マッチの $x_0$ がなくなるまで繰り返すか、到達した $X$ の頂点の集合 $S$ 上でホールの条件が破られる。なぜならそのとき到達したすべての $Y$ の頂点は $S$ へマッチし返されており、$|N(S)| \le |S| - 1$ が強制されるからである。仮定によりホールの条件は成り立つので、この矛盾は起こり得ず、したがって $X$ のすべての頂点は最終的にマッチされなければならない——これがケーニッヒ–エゲルヴァリの増加道の議論である。

$K_5$ と $K_{3,3}$ はそれ自体が非平面的である(オイラーの公式 $V - E + F = 2$ を使って直接確認できる)。辺をパスで置き換える細分は非平面性を保つ。1930年のクラトフスキの定理は驚くべき逆の主張である:これら二つのグラフだけが唯一の障害である。

(必要性:$K_5$、$K_{3,3}$、およびそれらの細分は非平面的である。) $V \ge 3$ を満たす任意の連結単純平面グラフを交差なく描いたとき、各面 $F$ は少なくとも $3$ 本の辺で囲まれ、各辺は高々 $2$ つの面に接するので、辺と面の接続関係を数えると $2E \ge 3F$ となる。オイラーの公式 $V - E + F = 2$ から得られる $F = E - V + 2$ を代入すると $2E \ge 3(E - V + 2)$、すなわち $E \le 3V - 6$ を得る。$K_5$ では $V = 5$ かつ $E = 10$ であり、$3V - 6 = 9 < 10$ に反するので $K_5$ は非平面的である。二部グラフ $K_{3,3}$ には奇閉路(したがって三角形)が存在しないため、各面は少なくとも $4$ 本の辺を必要とし、$2E \ge 4F$ と $V - E + F = 2$ を合わせると $E \le 2V - 4$ となる。$K_{3,3}$ は $V = 6$ かつ $E = 9$ であり $2V - 4 = 8 < 9$ に反するので、$K_{3,3}$ も非平面的である。

辺の細分(次数 $2$ の新しい頂点を通る道で辺を置き換える操作)は、グラフが交差なく平面に描けるかどうかを変えないので、$K_5$ または $K_{3,3}$ の細分を含むグラフはいずれも非平面的である。逆(十分性)は1930年にクラトフスキが証明したもので、$|V| + |E|$ に関する帰納法で進める:極小な非平面グラフ $G$ は $3$-連結でなければならず、1本の辺 $e$ を削除して得られる平面グラフ $G - e$ では、$e$ の両端点を囲む閉路の内側と外側の両方に交互に交わる弦が現れ、それが $G$ の内部に $K_5$ または $K_{3,3}$ の細分を強制する。