柯尼格引理

柯尼格引理(英語:König's lemma)为图论中的一个定理。

命题

给定具有无穷个顶点但每个顶点的有限的连通图G,则对G的任意顶点都至少存在一条无穷的简单路径

证明

G的任意顶点v1,因G连通,故v1到G的任意顶点都存在简单路径。由于G存在无穷个顶点,故存在从v1出发的一个无穷的简单路径集。考虑这个无穷简单路径集。因v1的度有限,故该无穷集必然有一个无穷子集通过v1的某个相邻顶点v2。同理,考察通过v1、v2的该无穷简单路径子集,因v2的度有限,故这些无穷简单路径又存在一无穷子集通过v2的某个相邻顶点v3,注意v3≠v1。以此类推,可得一无穷简单路径v1v2v3...。

说明

  • 上述证明为非构造证明,只說明存在性,但没有给出计算该路径的算法(事实上,该算法不存在)。
  • 此结论经常作为一个特例应用于:给定具有无穷个节点,但每个节点的分叉有限的树,则至少存在一条从根节点出发的无穷路径。反之,如果一颗树不存在无穷路径,且没有节点具有无穷分叉,则该树的节点数有限。
  • 虽然每个节点的度有限,但由于有无穷个节点,整个图的度可能没有上限(例如可构造以所有自然数为顶点的图,使得第i个节点的度为i)。