About: ケーニヒの補題

グラフ理論におけるケーニヒの補題はデネス・ケーニヒ (1936)によって示された定理で、無限グラフが無限長の道をもつための十分条件を与える。この定理のcomputability aspectsは数理論理学の計算可能性理論の研究者によって調べられてきている。この定理はや証明論においても重要な役割をもつ。