Are there a finite number of trees with $k$ leaves and no vertices of degree $2$?

Given a fixed positive integer $k$. Show that there are only finitely many trees containing $k$ leaves and zero vertices of degree $2$.

I tried to use the theorem related to rooted trees and tried to prove it by contradiction, but could not quite use the condition of having zero vertices of degree $2$.

Is it even related to rooted trees theorem or can it be proved by contradiction? Can we use the fact that a tree with $m$ edges has $m+1$ vertices?

Solution 1:

Consider an arbitrary tree with $k$ leaves and no vertices of degree $2$. Let $\epsilon$ represent the number of edges and $\nu_j$ represent the number of vertices with a degree of $j$ (so that $\nu_1=k$ and $\nu_2=0$). We know that $\sum_{j=1}^\infty j\nu_j=2\epsilon$ (since that's true for all graphs) and $\sum_{j=1}^\infty \nu_j=\epsilon+1$ (since it's a tree). So we can combine the equations as follows (where the index of the summations have been taken out).

$$\sum j\nu_j=2\big(\sum\nu_j-1\big)=2\sum \nu_j-2\\ 2\sum\nu_j-\sum j\nu_j=2\\\sum(2-j)\nu_j=2$$

The RHS is positive, so the LHS must be as well. The first few terms of the LHS is $\nu_1+0\nu_2-\nu_3-2\nu_4-\ldots.$ This could not be positive if $\nu_3+\nu_4+\nu_5+\ldots>\nu_1$. Since we know that $\nu_2=0$, we can conclude that a tree with $k$ leaves and no vertices of degree $2$ cannot have more than $2k$ vertices. Since the number of trees with fewer than $2k$ vertices is finite, we are done.

Solution 2:

This is easy to prove using the following two lemmata:

Lemma 1: The sum of the degrees of all vertices in a graph equals twice the number of edges.

Lemma 2: A tree with $n$ vertices has $n-1$ edges.

(The first lemma is a simple consequence of the definition of the degree of a vertex, i.e. the number of edges connected to it, and the fact that each edge connects to exactly two vertices. The second lemma can be proved by induction on the number of vertices: assuming that the lemma holds for all trees with $n-1$ vertices, take any tree with $n$ vertices and consider what happens when you merge any two adjacent vertices and remove the edge between them.)

Taken together these lemmata imply that, for any tree with $n$ vertices having the degrees $d_1, d_2, \dots, d_n$ respectively, $$\sum_{i=1}^n d_i = 2n - 2 \quad \text{and thus} \quad \sum_{i=1}^n (d_i - 2) = -2.$$ In other words, the sum of the degrees of all vertices minus two per vertex is the same (and equal to $-2$) for all trees!

In particular, we can see that the summand $d_i - 2$ is negative (and equal to $-1$ except for the degenerate case of the single-vertex tree) for leaves, zero for vertices of degree $2$ and positive (at at least one) for all other vertices. For the sum to equal $-2$, as it must, the positive contribution of each vertex with degree $d_i > 2$ must therefore be cancelled out by at least one leaf (and there need to be at least two extra leaves on top of that).

Thus, a tree with $k$ leaves can have at most $k - 2$ vertices of degree greater than $2$.

For a tree with $k$ leaves and no vertices of degree $2$, this implies that the total number of vertices in the tree can be at most $2k - 2$. And since the number of vertices in such a tree is thus bounded, and since there's only a finite number of possible ways of connecting any given number of vertices into a tree, this further implies that the total number of such trees is also bounded.

We can also see that, for this result to hold, it is essential that the number of vertices of degree $2$ be bounded (in your case by zero). Otherwise we could take any tree with $n > 1$ nodes and easily construct an infinite family of trees with the same number of leaves just by taking any pair of adjacent vertices and inserting an arbitrarily long linear chain of vertices of degree $2$ between them.