Infinite trees have no leaves

Often our mind conveniently ignores special or unlikely cases. But then completeness is an essential virtue of any mathematical proof.

I was listening to a lecture on graph theory, paying only partial attention since the speaker was covering very basic concepts. He started talking about trees: first he gave the different ways a tree can be defined; then he presented some properties of trees. For example, he said, “There is at least one vertex in a tree with degree one”. This is, of course, not completely correct. I am not sure why he made that mistake. The statement should be, ” There are at least two vertices in a tree with degree one”. This is pretty simple to prove.

The proof is by contradiction: let’s assume there are less than two vertices in a tree with degree one. So, there is either 1 vertex with degree 1 or none. Let’s consider both separately.

(1) If there are no degree 1 vertices in the tree, then every vertex has a degree of at least 2. So, the total degree of the tree is at least 2n, where ‘n’ is the number of nodes in the tree. Now, we know that the total degree of a graph is twice as much as the number of edges in the graph (Handshaking Lemma). So, in our tree there must be at least ‘n’ edges, which is not allowed by definition. Thus, we cannot have a situation where no nodes have a degree 1.

(2) If there is only one vertex with a degree 1, and every other vertex has at least a degree 2, the total degree of our tree is 2(n-1) + 1, which is an odd number. However, from the Handshaking Lemma we know that the total degree of a graph is always even. So, we have another contradiction. This situation is also not possible. So, we have to have at least two vertices with degree 1.

This is alright. But what brought my attention back to the lecture was what he said next: “This does not hold true for infinite trees.” Well, yes, it does not hold for infinite trees! In fact, we can also not prove that trees have no cycles when they are infinite. In fact, a lot of graph theorems that we prove or use don’t hold for infinite graphs. Sometimes we state it clearly, sometimes we don’t. It does not matter for most practical purposes. At the same time, it’s always a good idea not to ignore the theoretical completeness.

[Postscript: The basic result in Graph Theory about the relation between the total degree and the number of edges is called the Handshaking Lemma. It is the relation between the number of people in a party and the number of handshakes that result. (At least 2 people attend the party). I don’t like this analogy very much. Most graphs that result here are disconnected. It makes it complicated.]

Advertisement