Lemat Königa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj]

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