0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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,...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.