König's lemma

From Conservapedia
This is the current revision of König's lemma as edited by EdBot (Talk | contribs) at 04:03, 22 August 2010. This URL is a permanent link to this version of this page.

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

König's lemma (also spelled Koenig's lemma to avoid the trema) is a result in Zermelo-Fraenkel Set Theory and Graph Theory. It states that an infinite tree with finitely many branching degrees must have an infinite branch. Set theorists consider this to be an important transfinite generalization of the Pigeonhole Principle.

See also

Königsberg Bridges Problem