本帖最后由 hbghlyj 于 2025-3-3 16:21 编辑 König引理
给定具有无穷个顶点但每个顶点的度有限的连通图$G$，则对$G$的任意顶点都至少存在一条无穷的简单路径。
证明
对$G$的任意顶点$v_1$，因$G$连通，故$v_1$到$G$的任意顶点都存在简单路径。由于$G$存在无穷个顶点，故存在从$v_1$出发的一个无穷的简单路径集。考虑这个无穷简单路径集。因$v_1$的度有限，故该无穷集必然有一个无穷子集通过$v_1$的某个相邻顶点$v_2$。同理，考察通过$v_1$、$v_2$的该无穷简单路径子集，因$v_2$的度有限，故这些无穷简单路径又存在一无穷子集通过$v_2$的某个相邻顶点$v_3$，注意$v_3\neq v_1$。以此类推，可得一无穷简单路径$v_1v_2v_3...$。
说明
- 上述证明为非构造证明，只说明存在性，但没有给出计算该路径的算法（事实上，该算法不存在）。
- 此结论经常作为一个特例应用于树：给定具有无穷个节点，但每个节点的分叉有限的树，则至少存在一条从根节点出发的无穷路径。反之，如果一颗树不存在无穷路径，且没有节点具有无穷分叉，则该树的节点数有限。
- 虽然每个节点的度有限，但由于有无穷个节点，整个图的度可能没有上限（例如可构造以所有自然数为顶点的图，使得第$i$个节点的度为$i$）。
page 383 2.3.4.3. The "infinity lemma."
定理 K. （“无穷引理”）每个顶点具有有限度数的无限有向树都有一条通向根的无限路径，即一个顶点序列 $V_0, V_1, V_2, \ldots$，其中 $V_0$ 是根，并且对于所有 $j \geq 0$，有 $\operatorname{fin}\left(e\left[V_{j+1}\right]\right)=V_j$。
证明我们通过从有向树的根 $V_0$ 开始定义路径。假设 $j \geq 0$ 并且 $V_j$ 已被选择，且具有无限多的后代。根据假设，$V_j$ 的度数是有限的，因此 $V_j$ 有有限多个子节点 $U_1, \ldots, U_n$。这些子节点中至少有一个必须拥有无限多的后代，因此我们选择 $V_{j+1}$ 作为 $V_j$ 的这样一个子节点。
现在 $V_0, V_1, V_2, \ldots$ 是一条通向根的无限路径。
这里使用的论证本质上类似于证明经典的 Bolzano-Weierstrass 定理，“一个有界的无限实数集有一个聚点。” 正如 Kőnig 所观察到的，定理 K 的一种表述方式是：“如果人类永远不会灭绝，那么现在活着的某个人将有一条永不灭绝的后代线。”
大多数人在第一次遇到定理 K 时认为它是完全显而易见的，但经过更多的思考和对进一步例子的考虑，他们意识到它有一些深刻的东西。尽管树的每个节点的度数是有限的，但我们并没有假设这些度数是有界的（对于所有顶点小于某个数 $N$），因此可能会有度数越来越高的节点。至少可以想象，每个人的后代最终都会灭绝，尽管有些家族会延续一百万代，其他家族会延续十亿代，等等。事实上，H. W. Watson 曾经发表过一篇“证明”，在某些生物概率法则无限期地执行下，将来会有无限多的人出生，但每个家族线都会以概率一灭绝。他的论文 [J. Anthropological Inst. Gt. Britain and Ireland 4 (1874), 138-144] 包含了重要且深远的定理，尽管由于一个小错误导致他做出了这个声明，但他并没有发现他的结论在逻辑上不一致。
定理 K 的逆否命题直接适用于计算机算法：如果我们有一个算法，它定期将自身分成有限多个子算法，并且如果每条子算法链最终终止，那么该算法本身也会终止。 | 
