There is also a theorem of set theory called König's theorem. Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... There is also a proposition in graph theory called Königs lemma. ...

König's lemma or König's infinity lemma is a theorem in graph theory due to Denes König that states A theorem is a proposition that has been or is to be proved on the basis of explicit assumptions. ... In mathematics and computer science, graph theory studies the properties of graphs. ... Denes König, (September 21, 1884--October 19, 1944), was a Hungarian mathematician who worked in the field of graph theory. ...

if G is a connected graph with infinitely many vertices such that every vertex has finite degree (= number of immediately adjacent vertices), then every vertex of G is part of an infinitely long simple path. In mathematics and computer science, graph theory studies the properties of graphs. ... Infinity is a word carrying a number of different meanings in mathematics, philosophy, theology and everyday life. ... In mathematics, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. ...

A common special case of this is that every tree that contains infinitely many vertices, each having finite degree, has at least one infinite simple path. A tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...

Note that the vertex degrees have to be finite, but not bounded: it is possible to have one vertex of degree 10, another of degree 100, a third of degree 1000 etc.

The proof proceeds as follows. Start with the given vertex v₁. Every one of the infinitely many vertices of G can be reached from v₁ with a simple path, and each such path must start with one of the finitely many vertices adjacent to v₁. So there must be one of those adjacent vertices through which infinitely many vertices can be reached; pick one and call it v₂. Now, infinitely many vertices of G can be reached from v₂ with a simple path which doesn't use the vertex v₁. Each such path must start with one of the finitely many vertices adjacent to v₂. So there must be one of those adjacent vertices through which infinitely many vertices can be reached; pick one and call it v₃. Continuing in this fashion, an infinite simple path can be constructed (by mathematical induction). Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence. ...

One should note that this proof is not constructive, since it involves a proof by contradiction to establish that there exists an adjacent vertex from which infinitely many other vertices can be reached. Indeed the theorem cannot be proven in a constructive way. In the philosophy of mathematics, constructivism asserts that it is necessary to find (or construct) a mathematical object to prove that it exists. ... Reductio ad absurdum (Latin for reduction to the absurd, traceable back to the Greek ἡ εις το αδυνατον απαγωγη, reduction to the impossible, often used by Aristotle) is a type of logical argument where we assume a claim for the sake of argument, arrive at an absurd result, and then...

The Mizar project has completely formalized and automatically checked the proof of a version of König's lemma in the file TREES_2 (http://mizar.org/JFM/Vol3/trees_2.html). The Mizar system consists of a language for writing strictly formalized mathematical definitions and proofs, a computer program which is able to check proofs written in this language, and a library of definitions and proved theorems which can be referred to and used in new articles. ...