König's Lemma
Lemma
Let $G$ be an infinite graph which is connected and is locally finite.
Then every vertex lies on a path of infinite length.
Proof 1
Let $G$ be an infinite graph which is connected and is locally finite.
From Vertices in Locally Finite Graph, $G$ has an infinite number of vertices $v_1, v_2, \ldots, v_k, \ldots$, each of finite degree.
Let $\VV_k$ be the set of all vertices adjacent to $v_k$.
As $G$ is a connected graph, between $v_k$ and every other vertex of $G$ there exists at least one open path from $v_k$ to every other vertex of $G$.
Take any vertex of $G$ and call it $v_1$.
Let $\PP_1$ be the set of all paths from $v_1$.
Each element of $\PP_1$ must start with an edge joining $v_1$ to some element of $\VV_1$.
There must be some $v_r \in \VV_1$ such that there is an infinite path from $v_r$ in $G$ which does not pass through $v_1$. Otherwise, every path from $v_1$ would be finite, and since there is a path from $v_1$ to each other vertex of the graph, all vertices are contained within one of these finite paths. There are a finite number of paths from $v_1$, so all vertices of $G$ are contained within a finite set of finite sets, contradicting the assumption that $G$ is infinite.
By the axiom of dependent choice, we may pick one of the vertices of $V_1$ such that there exists an infinite path through it that does not include $v_1$, and call this $v_2$.
Each such infinite path must start with one of the elements of $\VV_2$.
Repeating the above argument shows that there is some $v_s \in \VV_2$ such that there is an infinite path from $v_s$ in $G$ which does not pass through $v_2$.
Thus we can construct by induction an infinite path.
The induction hypothesis states that there are infinitely many vertices which can be reached by a path from a particular vertex $v_i$ that does not go through one of a finite set of vertices.
The induction argument is that one of the vertices adjacent to $v_i$ satisfies the induction hypothesis, even when $v_i$ is added to the finite set.
The result of this induction argument is that for all $n$ we can choose a vertex $v_n$ as per the construction.
The set of vertices chosen in the construction is then a path, because each one was chosen to be adjacent to the previous one, and the construction guarantees that the same vertex is never chosen twice.
$\blacksquare$
Proof 2
Let $G$ be an infinite graph which is both connected and locally finite.
From Vertices in Locally Finite Graph, $G$ has an infinite number of vertices each of finite degree.
Let $v$ be a vertex of $G$.
Let $T$ be the set of all finite open paths that start at $v$.
Define the ordering $\preccurlyeq$ on $T$ as follows:
Let $\tuple {v_0, e_0, v_1, e_1, \ldots, v_m} \preccurlyeq \tuple {v'_0, e'_0, v'_1, e'_1, \ldots, v'_n}$ if and only if:
- $m \le n$
and:
- $\forall i < m: \tuple {v'_i, e'_i, v'_{i + 1} } = \tuple {v_i, e_i, v_{i + 1} }$
Observe that $T$ is a tree.
For each vertex $x$, let $\map E x$ be the set of all edges incident on $x$.
$\map E x$ is finite because $G$ is locally finite by definition.
For every $\tuple {v_0, e_0, v_1, e_1, \ldots, v_{n + 1} } \in T$ we have that $e_n \in \map E {v_n}$.
It follows that $T$ is finitely branching.
By definition of connectedness, to every vertex $x$ there is a walk $w$ from $v$.
Suppose $w = \tuple {v_0, e_0, v_1, e_1, \ldots, v_n}$ contains a cycle $\tuple {v_i, e_i, v_{i + 1}, \ldots, v_j}$ where $v_i = v_j$.
Then we can delete $\tuple {e_i, v_{i + 1}, \ldots, v_j}$ from $w$ to get a shorter walk from $v$ to $x$.
Repeatedly deleting cycles until none remain, we obtain an open path from $v$ to $x$.
There exist an infinite number of points in $G$, as, by definition of locally finite, $G$ is itself infinite.
We have just demonstrated that for each $x \in G$ there exists an open path from $v$ to $x$.
Hence $T$, the set of finite paths that start at $v$, is infinite.
By Kőnig's tree lemma, $T$ has an infinite branch $B$.
The union $\bigcup B$ is then an infinite path in $G$ that contains $v$.
$\blacksquare$
Proof 3
By Locally Finite Connected Graph is Countable, $G$ has countably many vertices.
Thus the result holds by König's Lemma: Countable.
$\blacksquare$
Axiom:Axiom of Countable Choice for Finite Sets
This theorem depends on Axiom:Axiom of Countable Choice for Finite Sets.
Although not as strong as the Axiom of Choice, Axiom:Axiom of Countable Choice for Finite Sets is similarly independent of the Zermelo-Fraenkel axioms.
As such, mathematicians are generally convinced of its truth and believe that it should be generally accepted.
Note
If the graph $G$ is assumed to be countably infinite, then the result will hold in pure Zermelo-Fraenkel set theory without any choice.
Source of Name
This entry was named for Dénes Kőnig.
Linguistic Note
In the conventional naming of König's Lemma, the diacritics on the ö in the König of König's Lemma and on the ő of Dénes Kőnig do not match.
While this is irritatingly confusing, unfortunately, it is how it is.