柯尼格引理

柯尼格引理（英語：König's lemma）為圖論中的一个定理。

命題

予遮的定具攏有無散个頂點毋過每一个頂點的度有限的連通圖 _ G _，著嘿 _ G _ 的任意頂點攏至少存在一條無散食的簡單路草。

證明

著 _ G _ 的任意頂點 _ v _ 一，因為 _ G _ 連通，故 _ v _ 一到 _ G _ 的任意頂點攏存在簡單路徑。因為 _ G _ 存在無散一个頂點，故事佇咧對 _ v _ 一出發的一个無窮的簡單路徑集。考慮這个散赤簡單路徑集。因為 _ v _ 一的度有限，故該無窮集必須是有一个無窮窮過 _ v _ 一的某一个相鄰頂點 _ v _ 二。同理，考察通過 _ v _ 一、_ v _ 二的該無窮簡單路徑子集，因為 _ v _ 二的度有限，故這寡無窮簡單路徑閣存在一無窮仔集通過 _ v _ 二的某一个相鄰頂點 _ v _ 三，注意 _ v _ 三 ≠ _ v _ 一。以此類推，會當一無窮簡單路徑 _ v _ 一 _ v _ 二 _ v _ 三 . . .。

說明

• 上述證明為非構造證明，干焦說明存在性，但是無算出計算路草的算法（事實上，該算法無存在）。
• 此結論定定做為一个特例應用佇樹仔：予散赤的所在，毋過逐个節點的分叉有限的樹仔，是至少愛佇咧一條對根節點出發的無窮路草。反之，若一粒樹仔無存在無散路草，而且無節點具有無窮分叉，則該樹仔的節點數有限。
• 雖然講每一个節點的度有限，但是因為有無窮的節點，規个圖的度可能無上限（比如講會當構造以所有自然數為頂點的圖，予第 _ i _ 個節點的度為 _ i _）。