Konig’s lemma

This post is about trees. Not real-life ones but mathematical trees, or more formally about acyclic connected graphs. Just as actual big skinny trees are tall, graph theoretic big skinny trees are also tall. The goal here is to prove this formally.

But first some definitions. A tree is called labeled if every vertex has been assigned a symbol, called its label. A fixed vertex in a tree may be labelled as r and referred to as its root. The level i in a tree is the collection of all vertices at a fixed distance i from the root. Admittedly these definitions are informal and may be formalized in terms of directed graphs.

An example of a labelled tree is given below:

Here r is the root and the vertex sets \{a,b\} and \{1,2,3\} are at level 1 and 2 respectively. Clearly this labeling is arbitrary and any other labeling is also possible.

We now prove our result. It is due to Konig, a Hungarian professor of mathematics, who had Erdos amongst his students. It is called a lemma because it was initially used by Konig to investigate another theorem (see this) . As often happens it has turned out to be a powerful tool to use on many other problems as well.

Lemma: If T is an infinite tree and each level of T is finite then T contains an infinite path.

Proof: Suppose T is a labeled tree with root r. Let L_0=\{r\}, L_1,L_2,\cdots be the levels of T. We construct our path by starting with r. Next we partition all vertices in levels higher then L_0 (i.e. all vertices in levels L_i where i>0) into as many finite parts as is the cardinality of L_1. In other words if L_1=\{v_1,\cdots v_n\} then we partition the vertices (there are infinitely many of them) in n parts: P_1,P_2\cdots P_n. This partitioning is done as follows: Any vertex w will be connected to r via some v_i owing to connectedness. We put w in P_i.

Now since we have partitioned infinitely many vertices in finitely many parts, one of the parts will contain infinitely many vertices.(This is also called the infinite pigeonhole principle). Let that part be P_j. Choose w_1=v_j as the next vertex in our under-construction path. Next we delete the vertex r and consider the component containing w_1. It is also an infinite tree with each level finite and having w_1 as its root. By a similar piece of reasoning, we get a vertex w_2 which is adjacent to w_1 and has infinitely many vertices corresponding to it. We continue building our path by choosing w_2 as a part of it. By induction we can continue and get an infinite path rw_1w_2\cdots. This proves the theorem.\Box

It should be noted that at each of the infinitely many stages of selecting the w_i we choose it out of a finite set: the finite set of vertices at that level each of which correspond to infinite parts in the current partitioning. There is no canonical way to make this choice. To ensure that this can be done we need to use a weak form of the axiom of choice: Let X\ne\emptyset and \mathcal{F}(X) be the collection of all finite subsets of it. Then there is a function f:\mathcal{F}(X)-\emptyset\to X such that f(x)\in x\forall x\in \mathcal{F}(X)-\emptyset. A curious fact is that Konig’s lemma in turn applies this weak form of the axiom of choice and so both of them are equivalent. While their equivalence can be established using the ZF axioms, obviously neither can be proved within ZF.



Filed under Combinatorics, Graph theory

3 responses to “Konig’s lemma

  1. Pingback: A ball game and Konig’s lemma | Notes on Mathematics

  2. Pingback: On abridged versions of Ramsey’s theorem | Notes on Mathematics

  3. Pingback: On unabridged versions of Ramsey’s theorem | Notes on Mathematics

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s