König's lemma or König's infinity lemma is a theorem in graph theory due to Dénes Kőnig (1936). It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.

PropertyValue
dbpprop:abstract
  • König's lemma or König's infinity lemma is a theorem in graph theory due to Dénes Kőnig (1936). It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory. Note that, although Kőnig's name is properly spelled with a double acute accent, the lemma named after him is customarily spelled with an umlaut.
  • Das Lemma von König oder Königslemma ist ein Theorem der Graphentheorie von Dénes Kőnig (1936). Die Berechenbarkeit des Lemmas wurde gründlich in der Mathematischen Logik erforscht. Dénes Kőnig wird korrekterweise mit Doppelakut geschrieben. Das nach ihm benannte Lemma wird aber üblicherweise mit einem Umlaut geschrieben.
  • Tout arbre infini à branchement fini a une branche infinie.
  • A gráfelméletben a Kőnig Dénes nevét viselő lemma a következőképpen hangzik: Legyen G egy végtelen sok csúcspontot tartalmazó összefüggő gráf, amelynek minden csúcsa véges fokú. Ekkor G bármely csúcsához található olyan végtelen út, mely áthalad ezen a csúcson. Egy gyakran előforduló speciális eset a következő: Minden olyan végtelen fagráf, melynek minden csúcsa véges fokú, tartalmaz végtelen utat.
  • Il Lemma di König in logica afferma che: Se un albero, in cui ogni nodo ha un numero finito di successori immediati, ha infiniti nodi allora in esso c'è anche un ramo infinito. Dimostrazione del lemma. Ogni nodo dell'albero avrà un'etichetta. Si dice che un nodo è prolungabile se e solo se da esso derivano rami di lunghezza finita e arbitraria, quindi la radice dell'albero è prolungabile. Supponiamo un nodo v prolungabile, implica che esiste un figlio di v prolungabile. Se f0 è prolungabile e se ogni nodo ha un figlio prolungabile esiste almeno un discendente che è prolungabile.
  • 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 istnieć nieskończona gałąź.
  • König引理为图论中关于无穷性的一个定理。
dbpprop:hasPhotoCollection
dbpprop:reference
dbpprop:title
  • König's Lemma
dbpprop:urlname
  • KoenigsLemma
dbpprop:wikiPageUsesTemplate
rdfs:comment
  • König's lemma or König's infinity lemma is a theorem in graph theory due to Dénes Kőnig (1936). It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.
  • Das Lemma von König oder Königslemma ist ein Theorem der Graphentheorie von Dénes Kőnig (1936). Die Berechenbarkeit des Lemmas wurde gründlich in der Mathematischen Logik erforscht. Dénes Kőnig wird korrekterweise mit Doppelakut geschrieben. Das nach ihm benannte Lemma wird aber üblicherweise mit einem Umlaut geschrieben.
  • Tout arbre infini à branchement fini a une branche infinie.
  • A gráfelméletben a Kőnig Dénes nevét viselő lemma a következőképpen hangzik: Legyen G egy végtelen sok csúcspontot tartalmazó összefüggő gráf, amelynek minden csúcsa véges fokú. Ekkor G bármely csúcsához található olyan végtelen út, mely áthalad ezen a csúcson. Egy gyakran előforduló speciális eset a következő: Minden olyan végtelen fagráf, melynek minden csúcsa véges fokú, tartalmaz végtelen utat.
  • Il Lemma di König in logica afferma che: Se un albero, in cui ogni nodo ha un numero finito di successori immediati, ha infiniti nodi allora in esso c'è anche un ramo infinito. Dimostrazione del lemma. Ogni nodo dell'albero avrà un'etichetta. Si dice che un nodo è prolungabile se e solo se da esso derivano rami di lunghezza finita e arbitraria, quindi la radice dell'albero è prolungabile. Supponiamo un nodo v prolungabile, implica che esiste un figlio di v prolungabile.
  • 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 istnieć nieskończona gałąź.
  • König引理为图论中关于无穷性的一个定理。
rdfs:label
  • König's lemma
  • Lemma von König
  • Lemme de König
  • Kőnig-lemma
  • Lemma di König
  • Lemat Königa
  • 柯尼格引理
owl:sameAs
skos:subject
foaf:page
is dbpprop:disambiguates of
is dbpprop:redirect of