Kőnig 引理

注意区分本文与 Kőnig 定理.

Kőnig 引理是图论、构造性数学、证明论里的重要定理. 它表现了无穷顶点的连通图中无穷简单路径的存在性.

1陈述与证明

定义 1.1. 令 $G$ 是有无穷多顶点, 每个顶点的度有限的连通图, 那么对于每个顶点都至少存在一条无穷的简单路径.

证明. 任意选取顶点 $v_{1}$ , 由于 $G$ 为连通图, 故存在从 $v_{1}$ 到任何 $G$ 的顶点的路径, 又因为 $v_{1}$ 的度有限, 所以必然存在无穷多路径以同一条边开始, 我们记其作 $v_{1} v_{2}$ .

同理又有 $v_{2} v_{3}$ ( $v_{1} \neq = v_{3}$ ).

以此类推, 得到了无穷的简单路径

v_{1} \to v_{2} \to \dots

$□$

注 1.2. 我们常见的形式有 $G$ 为树的情况, 也称为 Kőnig 树定理.

(...)

(...)

•