König's Lemma/Proof 2

From ProofWiki
Jump to navigation Jump to search

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

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$


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.


Source of Name

This entry was named for Dénes Kőnig.