檢視柯尼格引理的原始碼

{| class="wikitable" align="right"

|-

| style="background: #66CCFF" align= center|  '''<big>柯尼格引理</big> '''

|-

|[[File:柯尼格引理.jpg|缩略图|居中|[https://pic1.zhimg.com/80/v2-886372ac7c7f383a097b26cad6777088_720w.jpg 原图链接]]] 

|-

| style="background: #66CCFF" align= center|

|-

| align= light|

中文名: 柯尼格引理

外文名: König's lemma）

分 类: 图论、选择公理

领 域: 数理科学

|}
'''[[柯尼格引理]]'''（König's lemma）为图论
 
中的一个定理。<ref>[https://zhuanlan.zhihu.com/p/342435978 ],

知乎 , </ref>

==命题==

给定具有无穷个顶点但每个顶点的度有限的连通图G，则对G的任意顶点

都至少存在一条无穷的简单路径。
 
==证明==

对G的任意顶点v1，因G连通，故v1到G的任意顶点都存在简单路径。由

于G存在无穷个顶点，故存在从v1出发的一个无穷的[[简单路径集]]。

考虑这个无穷简单路径集。因v1的度有限，故该无穷集必然有一个无

穷子集通过v1的某个相邻顶点v2。同理，考察通过v1、v2的该无穷简

单路径子集，因v2的度有限，故这些无穷简单路径又存在一无穷子集

通过v2的某个相邻顶点v3，注意v3≠v1。以此类推，可得一无穷简单

路径v1v2v3...。

==说明==

上述证明为非构造证明，只说明存在性，但没有给出计算该路径的算

法（事实上，该算法不存在）。

此结论经常作为一个特例应用于树：给定具有无穷个节点，但每个节

点的分叉有限的树，则至少存在一条从根节点出发的无穷路径。反之

，如果一颗树不存在无穷路径，且没有节点具有无穷分叉，则该树的

节点数有限。

虽然每个节点的度有限，但由于有无穷个节点，整个图的度可能没有

上限（例如可构造以所有自然数为顶点的图，使得第i个节点的度为i

）。

== 参考来源 ==
{{reflist}}

[[Category:310 數學總論 ]]