König引理
维基百科，自由的百科全书
König引理为图论中关于无穷性的一个定理。
目录 |
[编辑] 命题
给定具有无穷个顶点但每个顶点的度有限的连通图G，则对G的任意顶点都至少存在一条无穷的简单路径。
[编辑] 证明
对G的任意顶点v1，因G连通，故v1到G的任意顶点都存在简单路径。由于G存在无穷个顶点，故存在从v1出发的一个无穷的简单路径集。考虑这个无穷简单路径集。因v1的度有限，故该无穷集必然有一个无穷子集通过v1的某个相邻顶点v2。同理，考察通过v1、v2的该无穷简单路径子集，因v2的度有限，故这些无穷简单路径又存在一无穷子集通过v2的某个相邻顶点v3，注意v3≠v1。以此类推，可得一无穷简单路径v1v2v3...。
[编辑] 说明
- 上述证明为非构造证明。只给出存在，但没有给出计算该路径的算法（事实上，该算法不存在）。
- 此结论经常作为一个特例应用于树：给定具有无穷个节点，但每个节点的分叉有限的树，则至少存在一条从根节点出发的无穷路径。
- 虽然每个节点的度有限，但由于有无穷个节点，整个图的度可能没有上限（例如可构造以所有自然数为顶点的图，使得第i个节点的度为i）。
[编辑] 反例
- 以下连通图（树）不存在无穷简单路径，因为顶点0的度为无限。
0
/|\...
1 2 3
[编辑] 应用
- 如果一颗树不存在无穷路径，且没有节点具有无穷分叉，则该树的节点数有限。
- 证明：反证。假设该树有无限个节点。使用König引理，必存在一无穷路径。矛盾。证毕。
