图论与组合 II · 图的基本理论
图 = 顶点 + 边，关系的最简数学模型。1736 年 Euler 用它一举解决七桥问题，顺手创立了这门学科。本页走主干：度与握手定理 → 连通与树 → Euler/Hamilton 两类回路（一个透明一个 NP 难的著名对照）→ 平面图与 Euler 公式（拓扑的示性数在离散世界的分身）。
1. 基本语言与握手定理
图 \(G = (V, E)\)；度 \(\deg(v)\) = 关联边数。有向/无向、简单图/多重图、完全图 \(K_n\)（边数 \(\binom n2\)）、二部图（顶点两色、边只跨色——判据：无奇圈）。
握手定理：\(\sum_{v} \deg(v) = 2|E|\)（每条边贡献两个度——双计数的最小样板）。推论：奇度顶点必有偶数个——"聚会上握过奇数次手的人有偶数个"；也是度序列可实现性的第一道闸门（例 1）。
2. 连通与树
树 = 连通无圈图，图论的骨架结构。五重等价刻画（背诵级）：\(n\) 顶点的图，以下等价——1. 连通无圈；2. 连通且恰 \(n-1\) 条边；3. 无圈且恰 \(n-1\) 条边；4. 任两点唯一路径；5. 极小连通（删任一边即断）。
生成树：含全部顶点的树子图（连通图必有）。最小生成树（MST）贪心算法：Kruskal（按边权从小到大，不成圈就收）/ Prim（从一点长大）——贪心为何正确：交换论证（若最优解不含当前最小安全边，换入它不会变差）——贪心算法正确性证明的标准范式（与 Huffman 同款，优化线的思想在离散世界续集）。Cayley 公式一嘴：\(n\) 个标号顶点的树有 \(n^{n-2}\) 棵（优雅得过分的计数结论，Prüfer 序列双射证明——上一页双计数的高级演出）。
3. Euler 与 Hamilton：透明与深渊的对照
Euler 回路（每条边恰走一次）：定理（Euler 1736） 连通图有 Euler 回路 \(\iff\) 全部顶点偶度（有 Euler 通路 \(\iff\) 恰两个奇度点）。 证明思路：必要性显然（每次过境一进一出消耗偶度）；充分性构造式——从任一点走圈、剩余部分递归接圈。七桥问题四个奇度点 ⇒ 无解，两百年悬案一行判决。
Hamilton 回路（每个顶点恰访一次）：看似孪生，实为深渊——判定是 NP-完全问题（没有已知的高效判据；与 Euler 的 \(O(E)\) 判定形成算法复杂性的教科书对照——"相似的问题可以有天壤之别的难度"）。只有充分条件可用：Dirac 定理——\(n \geq 3\) 且每点度 \(\geq \frac n2\) ⇒ 有 Hamilton 回路（"足够稠密必有环游"）。旅行商问题（TSP）= 加权版 Hamilton，组合优化的名题（优化 IV 分支定界的主战场之一）。
4. 平面图与 Euler 公式
平面图：可画在平面上使边不交叉。Euler 公式：连通平面图
（\(F\) 含无界外面；证明：对生成树归纳——树时 \(F=1, E=V-1\) ✓，每加一条边恰新增一个面。）这就是拓扑页 Euler 示性数 \(\chi\) 的离散原型（球面 \(\chi = 2\)——平面图即球面上的图，Gauss–Bonnet 页的 \(\chi\) 在此有了可数的定义）。
推论（非平面性判据）：简单平面图 \(E \leq 3V - 6\)（每面至少 3 边、每边贡献 2 面，双计数）⇒ \(K_5\) 非平面（\(10 > 9\)）；二部图加强为 \(E \leq 2V - 4\) ⇒ \(K_{3,3}\) 非平面（三户人家接三种管线必交叉——水电气难题的死刑判决）。Kuratowski 定理（陈述）：非平面 \(\iff\) 含 \(K_5\) 或 \(K_{3,3}\) 的剖分——两个最小反例就是全部障碍。
四色定理一嘴：平面图顶点四色可染（1976 计算机辅助证明——数学证明观念的分水岭事件；五色定理有纸笔证明，Euler 公式 + 归纳）。
5. 典型例题
例 1（度序列判定） 序列 \((3, 3, 3, 1)\) 可实现吗？度和 \(= 10\) 为偶 ✓ 但三个 3 度点要在 4 顶点图中各连 3 边，1 度点只能吸收一条——检查（Erdős–Gallai 或直接构造）失败：度和为偶是必要不充分。
例 2（Euler 应用：一笔画） 田字格（\(3\times3\) 顶点网格）能否一笔画？数奇度点：四条边中点度 3，共 4 个奇度点 \(> 2\) ⇒ 不能；去掉一条外边使奇度点降到 2 ⇒ 能，且必须从奇度点起笔。一笔画问题 = 数奇度点，小学谜题的完备判据。
例 3（平面性判断） Petersen 图（10 顶点 15 边）：\(E = 15 \leq 3V - 6 = 24\)——边数判据通过但它仍非平面（含 \(K_5\) 剖分）：必要条件不背锅，判死刑要用 Kuratowski。\(\blacksquare\)
下一页：图上的两大定理系统——匹配（Hall 婚配定理）与网络流（最大流最小割 = LP 对偶的组合化身），外加 PageRank 与 Markov 链的会师。