图、度与路径

在对度求和时,每条边恰好被计数两次——来自它的两个端点各一次。因此总和是偶数;偶度顶点本身对总和贡献的就是偶数,所以奇度顶点的个数必须是偶数。

任取一个有限图 $G = (V, E)$。构造由顶点 $v$ 是棱 $e$ 端点所构成的全部顶点-棱关联对 $(v, e)$ 的集合,并用两种方式对其计数。按顶点计数:每个顶点 $v$ 恰好贡献 $\deg(v)$ 个关联对(它触及的每条棱各贡献一个),故总数为 $\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$ 时,它沿一条棱进入,再沿另一条未用过的棱离开,恰好耗费 $v$ 的 $2$ 条关联棱;由于 $C$ 结束时恰好用了 $v$ 的每条棱一次,故每个顶点(包括起点/终点,此处最先出发的棱与最后到达的棱配对)的 $\deg(v)$ 必为偶数。

(充分性。)反过来,设连通图 $G$ 的每个顶点度数都是偶数。从任一顶点出发,沿未用棱贪心地行走;由于每个顶点度数都是偶数,每当路径进入一个非起点的顶点时,它总能再离开(偶数条关联棱不可能恰好减少到剩 $1$ 条未用棱),因此路径除了回到起点外不会卡住,由此得到一条闭合迹 $C$。若 $C$ 已用尽全部棱,则证毕。否则,由于 $G$ 连通,$C$ 上必有某顶点 $v$ 带有未用的关联棱;未用的棱在每个顶点处也都保持偶数度(去掉偶度闭合迹 $C$ 不改变奇偶性),故由同样论证它们构成另一条经过 $v$ 的闭合迹 $C'$。在 $v$ 处把 $C'$ 拼接进 $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$)会使匹配规模严格增加一个,这与沿此分支 $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$-连通的,删去一条棱 $e$ 后得到的平面图 $G - e$ 中,围绕 $e$ 两端点的圈在内外两侧都有交错的弦,从而在 $G$ 中迫使出 $K_5$ 或 $K_{3,3}$ 的细分。