Lemat Königa

Ten artykuł od 2023-08 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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łąź.