目录
1. 定义从未说过“有限”
回到顶点与边指南中的定义，看看它实际上说了什么：
G = (V, E) with E ⊆ [V]²一个顶点集，以及由它的二元子集构成的集合。其中没有任何地方提到大小。 V 可以是柯尼斯堡的四块陆地、整数、实数，或者所有有限二进制串的集合，定义丝毫不受影响。所谓无限图，就是顶点集为无限集的图，而本文的全部主题，就是在这种情况下哪些东西会悄然失效。
这并不是现代才有的细化。史上第一本图论著作是 Dénes König 1936 年的 Theorie der endlichen und unendlichen Graphen ，书名译为《有限图与无限图的理论》。无限图从这门学科的第一本教材起就在其中，而 Diestel 的 Graph Theory 至今仍用整整一章来讨论它们。
关键的一步是意识到，“有限”是一个你一直在用却没有看见的假设。大多数教材中的命题都采用“设 G 是一个有限图”这样的形式，而大多数标准证明技巧都在悄悄依赖它：
- 对顶点数做归纳需要有一个可以归纳的顶点数。
- 极值论证（“取度最大的顶点”“取最长的路径”）需要最大值或最长者存在。
- 计数论证需要计数结果是有限的数，而不是基数。
- 算法的终止需要搜索最终把图走完。
去掉有限性，上面每一项都必须用别的东西来替代。几乎在所有情况下，替代它们的都是紧致性：一个关于无限对象的命题，有时可以由关于其所有有限部分的命题拼合而成。第 5 节和第 6 节介绍的正是做到这一点的两个经典定理。
2. 有多大：可数、不可数、局部有限
“无限”并不是单一的大小，有三种独立的度量很重要。把它们混为一谈，是混乱的第一个来源。
| 度量 | 问的是什么 | 为何重要 |
|---|---|---|
| V 的基数 | 可数（ℵ0）还是不可数？ | 可数图可以枚举为 v1, v2, …，大多数构造都依赖于此 |
| E 的基数 | 有多少条边？ | 可数图至多有可数条边，所以 |E| ≤ ℵ0 ，其依据是 |V| = ℵ0 |
| 局部有限性 | 每个度都有限吗？ | 最重要的分界线：它是 König 引理的假设 |
若每个顶点的度都有限，就称图是局部有限的。这是一个真正独立于可数性的条件，两者的四种组合都会出现：
- 例如，双向射线，即沿两个方向无限延伸的路径，是可数且局部有限的：每个度都是 2。
- 再如无限正方形网格（位于
ℤ²上）是可数且局部有限的：每个度都是 4。电子表格、元胞自动机或拼贴式游戏世界实际上所在的就是这个图。 - 还有无限星图，即一个中心连接可数多片叶子，它是可数但不是局部有限的：中心的度是无限的。
- 不可数顶点集上的完全图是不可数且不是局部有限的。
- 由不可数多条互不相交的双向射线组成的图是不可数却局部有限的：顶点有不可数多个，但每个顶点的度仍然是 2。这是第四种组合，它表明两个条件都不能推出关于对方的任何结论。
有一个推论值得说明，因为它常常让人犯错：局部有限的图仍然可以是无限的，无限图也可以每个度都很小。局部有限性逐个约束每个顶点，却对图的大小只字未提。
3. 有限性在不知不觉中为你提供了什么
下面是一份如实的清单。这些都是标准结果和标准技巧，而每一项在无限图上失效都有具体的原因。
| 有限情形下的事实 | 在无限情形下 | 反例或原因 |
|---|---|---|
| 至少有 2 个顶点的树至少有 2 片叶子 | 失效 | 射线恰有一片叶子；双向射线一片也没有 |
| 某个顶点的度最大 | 失效 | 度为 1、2、3、…，没有任何顶点达到最大值 |
| 奇数度顶点的个数是偶数 | 失效 | 射线恰有一个，见第 4 节 |
| 对 |V| 归纳 | 无法使用 | 没有可以归纳的顶点数；超限归纳需要良序 |
| BFS 会终止 | 失效 | 它会永远枚举下去；它是一个半判定过程，见第 11 节 |
| 连通图有生成树 | 成立，但需要选择公理 | 见第 8 节 |
| k-可着色性 | 可由有限子图传递过来 | De Bruijn 与 Erdős，第 6 节 |
| 无限连通图含有射线 | 若局部有限则成立 | König 无穷引理，第 5 节；没有局部有限性则不成立 |
| Ramsey 型结果 | 往往更容易 | 无限版本有简洁的证明，也没有需要优化的界，第 10 节 |
其中两行值得立刻说明，因为它们最出人意料。
“某个顶点的度最大”不成立，而且原因是分析学中最平常的一个：自然数的无限集合不一定有最大元素。构造一个图，使其顶点的度为 1、2、3，如此无界地增长，那么 Δ(G) 就根本没有定义。因此，每一个以“设 v 是度最大的顶点”开头的极值论证，都悄悄假设了有限性，或者至少假设了一个界。
无限星图打破了 König 引理，这就是局部有限性出现在其陈述中的原因。星图是无限且连通的，但它最长的路径长度只有 2：叶子、中心、叶子。其中根本没有射线。一个无限度的顶点就足以摧毁结论，这说明这个假设在起实际作用，而不是技术上的讲究。
4. 握手推论的一行反例
这门学科最古老的定理是握手引理，而它的推论人人都记得：奇数度顶点的个数是偶数。在无限图上它是错的，而反例只需画一行。
取射线：顶点 v0, v1, v2, … ，相邻顶点之间各有一条边。
v0 ── v1 ── v2 ── v3 ── v4 ── ⋯
deg(v0) = 1 奇数
deg(vi) = 2 偶数，对每个 i ≥ 1
奇数度顶点：恰好一个。有限情形的推论说这个数必须是偶数。值得准确说明哪些东西保留了下来，因为答案比一句笼统的“失效”更有意思。
这个等式 ∑ deg(v) = 2|E| 并没有变成错的，而是变得空洞。两边都是基数，而对于无限基数 κ 有 2κ = κ，所以这个恒等式平凡地成立，却不提供任何信息。真正失效的，是建立在它之上的奇偶性论证。那个论证把有限和分成奇数部分和偶数部分，推出奇数部分的项数为偶数，而让这一步合法的是和的有限性，不是等式本身。
这个教训可以推广：当一个有限定理在无限图上失效时，通常失效的不是命题本身，而是证明技巧，而这种技巧通常就是计数。
5. König 无穷引理：第一座桥梁
如果大多数证明依赖的是有限性，那么有意思的问题是什么能取代它。第一个也是最有用的答案，是 König 在 1927 年发表的一个引理，比他的教材早了九年。
König 无穷引理。每个无限、连通且局部有限的图都含有一条射线，也就是一条无限路径 v0, v1, v2, … ，其中没有重复的顶点。
证明是把鸽巢论证无限次地重复，值得一看，因为这种结构在整个无限组合学中反复出现。
从任意顶点 v0出发。图是无限且连通的，因此从它出发可以到达无穷多个顶点。图是局部有限的，因此 v0 只有有限个邻居。删除 v0 后，剩下的无穷多个顶点被分到有限多块中，由鸽巢原理，至少有一块是无限的。走进这一块，你就回到了与起点完全相同的处境。无限重复下去，就得到 v0, v1, v2, …，而且由于每一步都进入尚未访问的区域，没有顶点会重复。
两个假设都在起作用，去掉任何一个，结论都会失效：
- 去掉局部有限性，无限星图就是反例：无限、连通，而它最长的路径只有 3 个顶点。
- 去掉无限性，就没有什么需要证明的了。
这个引理的影响远超图论。在树的形式下，即“无限且有限分叉的树有一条无限的分支”，它是逻辑学中紧致性论证的组合核心，也正是它让我们能够断言：具有无穷多个有限状态的计算必定有一条无限的运行。这与命题逻辑紧致性定理背后的思想相同，下一节正是由此而来。
6. De Bruijn 与 Erdős：可着色性的传递
第二座伟大的桥梁，把一个可以在有限部分上检验的性质提升到整个无限图。
De Bruijn-Erdős 定理（1951）。对于有限的k，无限图是k-可着色的，当且仅当它的每个有限子图都是k-可着色的。
“仅当”这个方向是平凡的：整个图的着色限制到每个子图上仍是着色。实质内容在另一个方向，而且确实令人惊讶。它说的是可着色性这种同时约束无穷多个顶点的全局条件，完全由有限窗口中发生的事情决定。“在无穷远处”不会出现任何新的问题。
有两点限制很重要，而通俗介绍通常会略过：
- 颜色数必须有限。这个定理针对的是固定的有限
k。它并没有说：若一个图的所有有限子图都能用有限多种颜色着色，这个图本身就能用有限多种颜色着色。 - 它需要某种选择原理。标准证明借助紧 Hausdorff 空间的 Tychonoff 定理、Zorn 引理或超滤子引理。在完全不含选择公理的 Zermelo-Fraenkel 集合论中，这个定理是不可证明的。De Bruijn 和 Erdős 与几乎所有人一样，在可以使用选择公理的前提下工作。
对于为无界系统建模的人来说，实际含义是：如果你的约束能表示成使用固定有限调色板的着色，就可以在有限片段上验证它，并推断整体也成立。这正是紧致性论证赋予你的许可，也是有限模型检验有时能对无界运行下结论的原因。
7. 射线、双向射线与端
有限图论没有用来描述“图在远处是什么样子”的词汇，因为有限图没有“远处”。无限图论需要这样的词汇，而标准构造出自 Halin。
- 所谓射线，是指单向无限路径
v0, v1, v2, …。König 引理说，每个无限、连通、局部有限的图都有一条射线。 - 所谓双向射线，是指以整个
ℤ为下标的双向无限路径。它是一棵完全没有叶子的无限树，而这恰恰是任何有限树都做不到的。 - 所谓端，是射线的等价类，其中若没有任何有限顶点集能把两条射线分开，就认为它们等价。端是对“这个图朝多少个不同方向延伸到无穷远”这一问题的形式化回答。
这个概念通过例子比通过定义更容易体会：
| 图 | 端数 | 解读 |
|---|---|---|
| 射线 | 1 | 它只朝一个方向延伸 |
| 双向射线 | 2 | 两个方向；去掉任意有限的一段都会留下两半无限的部分 |
无限网格 ℤ² | 1 | 去掉任何有限的一块，仍然只留下一个连通的无限区域，所以所有射线都等价 |
| 无限二叉树 | 不可数多个 | 每条无限分支对应一个端，而分支与无限二进制串一一对应 |
网格这一项最有启发性。直觉上平面向四面八方延伸，所以你也许会以为它有许多端，但定义问的是能否通过去掉有限个顶点把射线分开，而在网格中做不到：只要走得足够远，总能绕过任何有限的洞。答案是一个端，而决定答案的是定义，不是图像。
8. 生成树与选择公理
每个有限连通图都有生成树，证明是一个两行的贪心论证：不断删除位于环上的边，直到没有环为止。由于边数有限，这个过程必然终止。
无限情形的命题依然成立，但原因不同，而且深刻得多：
每个连通图都有生成树。对无限图而言，这需要选择公理，而且这个命题实际上与选择公理等价。
通常的证明把 Zorn 引理应用于按包含关系排序的无环子图族，这本身就是一种伪装的选择原理。蕴含关系是双向的，也就是说“每个连通图都有生成树”不只是选择公理的推论，而是与它同样强，这是一个真正引人注目的结果：一个看似平淡无奇的图论命题，竟是某个集合论公理的众多等价形式之一。
它的实际意义很小，概念意义却很大。你写的任何算法都不会受影响，因为程序接触的图要么是有限的，要么至少是可计算地给出的。但它精确标出了无限图论从组合学变成集合论的地方，也解释了为什么关于无限图的书会仔细说明自己采用了哪些选择原理。
同样的模式在别处也会出现。好几个对有限图来说稀松平常的命题，在无限版本中依赖于选择公理，或者独立于基本公理，这也是为什么 De Bruijn-Erdős 定理同样带有选择假设。
9. Rado 图：统御一切的图
无限图不只是规模更大的有限图。其中一些的行为方式在有限情形中根本没有对应物，最清晰的例子就是 Rado 图。
如果可数图满足下面的条件，就说它具有扩展性质：对任意一对互不相交的有限顶点集 U 和 W，都存在一个顶点与 U 中的每个顶点相邻，且与 W中的任何顶点都不相邻。于是：
唯一性。任意两个具有扩展性质的可数图都同构。在同构意义下，这样的图恰有一个： Rado 图，也称随机图 R。
它之所以叫随机图，是故事的后半部分。Erdős 和 Rényi 证明，如果对一个可数无限集中的每对顶点独立地以概率 1/2 决定是否连边，所得结果以概率 1 满足扩展性质。因此：
对可数无限集中的每一对顶点抛一枚均匀硬币。
以概率 1，得到的图就是 Rado 图。
换一种方式再做一次。在同构意义下，你得到的仍是 Rado 图。本质上只有一个可数无限随机图。有限图完全没有类似的现象： n 个顶点上的随机图千差万别，有意思的问题都是哪些性质以高概率成立。Rado 图还把每个有限图和每个可数图都作为导出子图包含在内，这使它成为可数图中的万有图。
对实际使用者来说，要点不在构造本身，而在于它带来的警示：在有限图上形成的直觉，到了无限情形不仅在数量上出错，而且在性质上出错。“随机”不再意味着“多样”，而是意味着“规范”。
10. 无限反而更容易的时候
人们也许会合理地认为无限图总是更难。有时情况恰恰相反，Ramsey 理论就是标准例子。
| 有限 Ramsey 定理 | 无限 Ramsey 定理 | |
|---|---|---|
| 陈述 | 对每个 k 都存在 N ，使得 KN 的边的任意 2-着色都含有单色的 Kk | 可数无限顶点集上完全图的边的任意 2-着色，都含有一个无限的单色完全子图 |
| 证明 | 更难，而且界的问题有大量文献 | 一个简短的鸽巢论证 |
| 未解决问题 | 连 R(5,5) 都尚未知 | 陈述简洁，问题已解决 |
Ramsey 在 1930 年的论文中证明了两者。无限版本之所以更容易，恰恰是因为它不要求界：你永远不必说出单色结构出现在多远的地方，只需说明它会出现。可以用与 König 引理同类的紧致性论证从无限版本推出有限版本，但得到的界非常糟糕，这就是有限 Ramsey 理论成为一个独立且困难得多的领域的原因。
一般的教训是：无限的命题往往更简洁，因为它们不是定量的。当一个有限定理因为界而困难时，它的无限类比可能简单得多，却仍能告诉你有用的东西。
11. 计算中的无限图
无限图并不是纯粹数学上的消遣。它们在计算机科学中不断出现，通常是隐式的，而且总以同一种伪装出现：一个你从不去构建的图。
- 状态空间。图灵机、带无界整数的程序或带无界队列的协议，其格局图都是无限的。对这样的系统做模型检验，恰恰就是研究一个由有限描述给出的无限图。
- 格点与网格。无界瓦片地图上的寻路、元胞自动机和图像格点都位于
ℤ²上，它是一个无限的局部有限图。 - 博弈树。没有步数限制的博弈的完整博弈树是无限的；搜索算法只探索它的一个有限前缀。
- Cayley 图。一个无限群配上选定的生成元集，就给出一个无限的点传递图，几何群论正是通过这些图及其端来研究群的。
- 递归定义的结构。所有有限字符串在“追加一个字符”操作下构成的图是一棵无限树，可计算性理论中通常就是把 König 引理用于这个对象。
工程上的后果是一个清晰的区分：
在无限的局部有限图上，搜索变成半可判定的。从s出发的广度优先搜索，若存在到t的路径就会找到它，若不存在则会永远运行下去。局部有限性保证每一层都是有限的，因此搜索能在有限时间内到达每个距离。它能确认可达性，却永远无法否定可达性。
这种不对称正是为什么在无限图上应该选择 BFS 而不是 DFS ：BFS 按距离顺序探索，能在有限时间内到达任何可达顶点，而 DFS 可能沿一条无限分支一路向下，永不返回。迭代加深之所以存在，也是出于同样的原因。要保证终止，还需要额外的东西，比如局部有限性加上一个界、一个单调递减的度量，或者状态空间的有限抽象。
12. 常见错误
- 假设最大值或最小值存在。 “取度最大的顶点”和“取最长的路径”都预设了有限性或明确的界。在无限图上，它们可能根本不指向任何东西。
- 使用奇数度推论。射线恰有一个奇数度顶点，正如第 4 节所示。
- 对顶点数做归纳。不存在这样的数。超限归纳可以用，但需要良序，而这又是对选择公理的一次诉诸。
- 忘记 König 引理中的局部有限性。无限星图是无限的、连通的，却不含射线。这个假设不是装饰。
- 期待终止。无限图上的搜索是半可判定的，因此“无路径”的答案永远不会到来。要么显式限制搜索，要么使用有限抽象。
- 在无限图上运行 DFS。一条无限分支就会把它吞没。请使用 BFS 或迭代加深。
- 套用有限的计数结果。凡是通过计数顶点、边或关联关系证明的结论都需要重新审视；凡是通过紧致性证明的结论通常依然成立。
- 把“无限”当作一回事。可数与不可数、局部有限与非局部有限是相互独立的，几乎每个定理都取决于你面对的是哪种组合。
13. 术语表
| 术语 | 含义 |
|---|---|
| 无限图 | 顶点集为无限集的图；定义 G = (V, E) 保持不变 |
| 可数图 | |V| = ℵ0，因此顶点可以列为 v1, v2, … |
| 局部有限 | 每个顶点的度都有限；与图有多大无关 |
| 射线 | 没有重复顶点的单向无限路径 |
| 双向射线 | 以整数为下标的双向无限路径 |
| 端 | 射线的等价类，若没有有限顶点集能把两条射线分开，它们就等价 |
| König 无穷引理 | 每个无限、连通、局部有限的图都含有射线 |
| De Bruijn-Erdős 定理 | 对有限的 k，无限图的 k-可着色性可由其所有有限子图的 k-可着色性推出 |
| Rado 图 | 唯一具有扩展性质的可数图；可数随机图 |
| 扩展性质 | 对不相交的有限集 U 和 W，存在一个顶点与 U 中所有顶点相邻而与 W 中任何顶点都不相邻 |
| 紧致性论证 | 由所有有限子图上的某个性质推出无限图具有同一性质 |
| 半可判定 | 肯定的答案会在有限时间内得到；否定的答案可能永远不会到来 |
14. 常见问题
什么是无限图？
顶点集为无限集的图。定义 G = (V, E)（其中 E 是 V 的二元子集构成的集合）对大小没有任何要求，所以定义无需修改。改变的是哪些定理和证明技巧仍然适用：对顶点数的归纳、选取最大值的极值论证以及计数论证都依赖有限性，而 König 无穷引理这类紧致性论证依然成立。
局部有限是什么意思，为什么如此重要？
若每个顶点的度都有限，就称图是局部有限的，这与图本身是否有限无关。它之所以重要，是因为它是 König 无穷引理的假设：每个无限、连通、局部有限的图都含有一条射线。去掉这个假设，结论立刻失效，因为无限星图是无限且连通的，而它最长的路径只有三个顶点。计算中出现的大多数无限图，例如整数网格以及每个状态只有有限种走法的状态空间，都是局部有限的。
握手引理在无限图上成立吗？
没有什么用处。等式本身变得空洞：两边都是无限基数，而把无限基数加倍不会改变它，所以它平凡成立，却不包含任何信息。人们真正在用的推论，即奇数度顶点的个数为偶数，则干脆是错的。单向无限路径恰有一个度为 1 的顶点，其余顶点的度都是 2，所以恰有一个奇数度顶点。
BFS 或 DFS 能在无限图上运行吗？
BFS 在有限的意义上可以：在局部有限图上，它能在有限时间内到达距离为 d 的每个顶点，所以只要存在到目标的路径就一定能找到。若不存在路径，它不会终止，这使得可达性是半可判定而非可判定的。DFS 更糟，因为它可能沿一条无限分支一路向下永不返回，所以可能错过离起点只有一步之遥的目标。请使用 BFS 或迭代加深；如果无论如何都需要一个答案，就显式地限制搜索。
真的只有一个可数无限随机图吗？
在同构意义下，是的。对每条可能的边独立地以二分之一的概率决定是否存在，构造一个可数无限图，结果以概率 1 具有扩展性质。任意两个具有该性质的可数图都同构，所以几乎所有这样的随机构造都得到同一个图，即 Rado 图。它还是万有的：每个有限图和每个可数图都作为导出子图出现在其中。有限随机图没有任何类似现象。
无限图在实践中重要吗，还是纯粹理论性的？
它们不断出现，而且总以一个你从不构建的图的形式出现。带无界整数的程序的格局空间、无界游戏世界的瓦片地图、没有步数限制的博弈树，以及所有有限字符串构成的树，都是由有限描述给出的无限图。模型检验、终止性分析和无界状态空间中的搜索，在形式上都是无限图问题。实际的后果是搜索变成半可判定的，所以算法需要明确的界或有限抽象才能保证给出答案。
15. 参考文献
以上定义、定理和归属均出自以下文献，按时间顺序排列。
- König, D. (1927). "Über eine Schlussweise aus dem Endlichen ins Unendliche." Acta Litterarum ac Scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae, Sectio Scientiarum Mathematicarum （Szeged）3，121 至 130 页。无穷引理。
- Ramsey, F. P. (1930). "On a Problem of Formal Logic." Proceedings of the London Mathematical Society s2-30，264 至 286 页。同时包含有限和无限 Ramsey 定理。
- König, D. (1936). Theorie der endlichen und unendlichen Graphen. 莱比锡：Akademische Verlagsgesellschaft。第一本图论著作，书名中已经点出了两种情形。
- de Bruijn, N. G. and Erdős, P. (1951). "A Colour Problem for Infinite Graphs and a Problem in the Theory of Relations." Indagationes Mathematicae 13，369 至 373 页。
- Erdős, P. and Rényi, A. (1963). "Asymmetric Graphs." Acta Mathematica Academiae Scientiarum Hungaricae 14，295 至 315 页。其中指出可数随机图在同构意义下是唯一确定的。
- Halin, R. (1964). "Über unendliche Wege in Graphen." Mathematische Annalen 157，125 至 137 页。图的端的理论。
- Rado, R. (1964). "Universal Graphs and Universal Functions." Acta Arithmetica 9，331 至 340 页。万有可数图的显式构造。
- Cameron, P. J. (1997). "The Random Graph." 载于 R. L. Graham 和 J. Nešetřil（编）， The Mathematics of Paul Erdős II，333 至 351 页。柏林：Springer。关于 Rado 图及其性质的综述。
- Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184。纽约：Springer。
- West, D. B. (2001). Introduction to Graph Theory，第 2 版。Upper Saddle River：Prentice Hall。
- Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244。伦敦：Springer。
- Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。第 8 章专门讨论无限图、射线和端。