柯尼格引理
外觀
此條目沒有列出任何參考或來源。 (2015年12月7日) |
柯尼格引理(英語: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)。