Proving the number of leaves of a tree. (Graph Theory)

Question

Prove that if a tree has $n$ vertices (Where $n\geq 2$)and no vertices has degree of $2$, then $T$ has at least $\frac{n+2}{2}$ leaves.

Prove by contradiction

Suppose that $T$ has less than $\frac{n+2}{2}$ leaves and arrive at a contradiction. Given this fact,i deduce that $T$ has more than or equal to $n-\frac{n+2}{2}=\frac{n-2}{2}$ internal vertices.

Rewriting these facts $T\le$$\frac{n}{2}$ leaves while $T\geq\frac{n}{2}-1 $ internal vertices. But since the no of internal vertices cannot be equal to the number of leaves then the only way for the above condition to hold is when

$T$ has $\frac{n}{2}$ leaves

and

$T$ has $\frac{n}{2}-1 $ internal vertices

or in another words

$\frac{n}{2}-1 $ internal vertices gives rise to $\frac{n}{2}$ leaves

Clearly this has to be a full binary tree which satisfy this property. But we know that a binary tree has a degree of $2$ at its root which is a contradictio to the above statement. Hence proving the above statement. Is my proof correct. Could anyone explain. Thanks

Answer 1

Some problems in your writeup: If $l$ is the number of leaves of $T$, you cannot conclude that $l \leq \frac{n}{2}$, but only $l \leq \frac{n+1}{2}$ (in case $n$ is odd). And so, the number of internal vertices is $n - l \geq \frac{n-1}{2}$ (not $\frac{n}{2} - 1$).

A priori, I see no reason why the number of internal vertices can't be equal to the number of leaves: this is something that needs to be proved (it's certainly not true for trees in general.) It also doesn't seem clear that it "must be" a full binary tree.

You'd be better off just looking at the degree sum and finding a contradiction, like this:

---

If $T$ has strictly fewer than $\frac{n+2}{2}$ leaves, then it has strictly more than $\frac{n-2}{2}$ internal vertices, which all have degree at least 3.

Hence its degree sum is strictly more than $$ \frac{n+2}{2} + 3\frac{n-2}{2} = \frac{4n - 4}{2} = 2n - 2. $$ But in any graph, the degree sum is twice the number of edges, and any tree has $n - 1$ edges, so this degree sum must be exactly $2n - 2$. Contradiction.

Answer 2

I am thinking at induction.

• I will use the notation z for the numbers of leaves in a tree

• Let's assume the statement is true for n=k (a tree with k vertices and $z_k$ leaves):

  $z_k\ge\frac{K+2}{2}$

• Now I have to prove that for n=k+1 the statement is also valid. This means that I will add one vertex at a tree with k vertices. Where can I add it? There are 2 cases:

  (1) As a leaf vertex (the degree of the new vertex can only be 1)

  In this case:

  $z_{k+1}=z_k+1\ge\frac{K+2}{2}+1=\frac{(k+1)+2}{2} $

  (2) As an inner vertex

  In this case the degree is at least 2 because it has to be connected with a parent vertex and a child one. But in your problem the degree cannot be 2. So I cannot add an inner vertex without also adding at least one new leaf with it. In this scenario n=k+1 is not possible. I can only have n=k+2,k+3,...