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
Best Answer
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.