Lema de Konig
De Wikipedia, a enciclopédia encyclopedia
O Lema de König ou Lema da Infinitude de König é um teorema da teoria dos grafos creditado a Dénes Kőnig (1936). Ele fornece uma condição suficiente para que um grafo infinito tenha um ramo infinitamente longo. Os aspectos desse teorema relacionados à computabilidade têm sido minuciosamente estudados por pesquisadores da lógica matemática, especialmente na teoria da computabilidade. Tal teorema também desempenha papeis importantes na matemática construtiva e na teoria da prova.