Lemat Königa

Lemat Königa to lemat mówiący o tym, że jeśli drzewo jest nieskończone, a każdy węzeł ma skończoną liczbę dzieci, to musi w tym drzewie istnieć nieskończona ścieżka prosta.

Dowód

Pod korzeniem znajduje się nieskończona liczba podwęzłów. Wybierzmy to z dzieci, pod którym również znajduje się nieskończona liczba podwęzłów. Ponieważ liczba wszystkich podwęzłów korzenia – czyli liczba wszystkich węzłów-dzieci (która jest skończona) plus suma liczb wszystkich ich podwęzłów jest nieskończona, musi zawsze być choć jeden taki węzeł. Powtórzmy operację dla każdego kolejnego wybranego węzła. Procedura ta nigdy się nie skończy, bo przeczyłoby to założeniu, że pod danym węzłem jest nieskończona liczba podwęzłów. Znaleźliśmy w ten sposób nieskończoną gałąź.