Talk:König's Lemma

Cardinality

The note at the bottom says that if the graph is countable, then DC is not needed. If I'm not mistaken, however, every locally finite, connected graph must be countable, and that DC is never needed:

Choose an arbitrary vertex $q$.

Let $S_0 = \{ q \}$.

Let $S_{n+1}$ be the set of all vertices that are adjacent to an element of $S_n$ but not adjacent to any element of $S_k$ for $k < n$.

That is, $S_n$ is the set of vertices whose shortest path(s) to $q$ have $n$ edges.

Since the graph is connected, every vertex of the graph is in $\ds \bigcup_{n \in \N} S_n$.

But by the Axiom of Countable Choice for Finite Sets, $\ds \bigcup_{n \in \N} S_n$ is countable, so there are countably many vertices in the graph. No further choice is required to prove that there are countably many edges.

I believe it should be possible to prove this theorem using Dependent Choice for Finite Sets. --Dfeuer (talk) 18:14, 27 May 2013 (UTC)

Indeed, the set of minimal-length finite paths that start at $q$ (that is, paths that start at $q$ and end at some vertex $v$ with the property that there is no shorter path from $q$ to $v$) can be arranged into a tree in a natural way, and the tree lemma should then apply. --Dfeuer (talk) 18:23, 27 May 2013 (UTC)

More intuitively still, finite sequences $(x_n)$ such that $x_n \in S_n$ and $x_{n+1}$ is adjacent to $x_n$ for each $n$. I guess I'll have to write this up. --Dfeuer (talk) 18:28, 27 May 2013 (UTC)

Oriented tree

There are two ways to represent an oriented tree. One was is to direct all edges toward the root (which is what Knuth does). The other is to direct them all away from the root (which seems more intuitive to me, personally, but that's of little consequence). Do you have references that will give you a sense of which way is more common these days? --Dfeuer (talk) 21:53, 27 May 2013 (UTC)

I don't even know what an oriented tree is. --prime mover (talk) 21:54, 27 May 2013 (UTC)

Knuth 2.3.4.2:

An oriented tree (see Fig. 34), sometimes called a "rooted tree" by other authors, is a directed graph with a specified vertex $R$ such that:

$(a)\quad$ Each vertex $V \ne R$ is the initial vertex of exactly one arc, denoted by $e[V]$.

$(b)\quad$ $R$ is the initial vertex of no arc;

$(c)\quad$ $R$ is a root in the sense defined above (that is, for each vertex $V \ne R$ there is an oriented path from $V$ to $R$).

Knuth proceeds to prove that the undirected graph corresponding to an oriented tree is connected and acyclic (that is, it is a tree). He then proves also that every non-empty rooted tree corresponds to an oriented tree. --Dfeuer (talk) 22:05, 27 May 2013 (UTC)

We have Definition:Rooted Tree on this site - did you use Oriented Tree as a deliberate attempt to confuse? Because it worked. I give up. This website is now officially yours because I can't keep up with you any more. --prime mover (talk) 22:16, 27 May 2013 (UTC)

No, I did not. Our definition of rooted tree is actually different: it's just a tree (undirected) with a distinguished "root" vertex. An oriented tree is a directed graph that (by hook or by crook of definition) corresponds to a rooted tree. --Dfeuer (talk) 22:30, 27 May 2013 (UTC)

Proof 1

Proof 1 has some serious problems. The troubled paragraph claims to prove that there is an infinite path from some point (it doesn't really matter where). From that, it's straightforward to prove that the is an infinite path starting anywhere you like, with no additional need for choice:

Let $v_0$ be a vertex.

Let $p = r_0, r_1, \dots$ be an infinite path.

By connectedness, there is a path $q = s_0, s_1, \dots, s_n$ where $s_0 = v_0$ and $s_n = r_0$.

Let $k$ be the first natural number such that there exists $i \in \N$ such that $s_k = r_i$.

Then $s_0, \dots, s_k, r_{i+1}, \dots$ is the path we desire.

The problem is that the proof in the troubled paragraph doesn't actually seem to work out at all.

Do you want to try to figure out a way to fix this, or should we delete Proof 1? --Dfeuer (talk) 22:25, 27 May 2013 (UTC)