柯尼格引理檢視原始碼討論檢視歷史

柯尼格引理

原圖鏈接

中文名: 柯尼格引理 外文名: König's lemma） 分 類: 圖論、選擇公理 領 域: 數理科學

柯尼格引理（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

）。