Proof - A tree $T$ has a vertex of degree n and the others have degree $<n$. T has at least n leaves

Question

I tried to think about some characteristics of the trees, for example, they have a number of edges equal to $|\text{Vertices}|-1$ and of course the handshaking lemma but I couldn't find properly logical reasoning. Any help?

Answer 1

Let the tree be $T$, vertex with degree $n$ be $u$. Let the vertices adjacent to $u$ be $v_1, v_2,\cdots v_n$. Delete the vertex $u$. You'll get $n$ new components(trees), $T_1, T_2,\cdots T_n$. This is because no vertex in $T_i$ is adjacent to any vertex in $T_j$, $i\neq j$. WHY? Suppose they were adjacent. Let "that" vertex in $T_i$ be a, and in $T_j$ be $b$ $\implies$ you can go from $u$ to $a$, then $a$ to $b$ and then from $b$ to $u$$\implies$ cycle, which isn't possible. Hence, $T_i$s are components. Further, since $T$ was a tree, $T_i$s will also be trees.

Note that if $T_i$ has only a single vertex, it was already a leaf in $T$. Suppose there are $k$ such $i$$\implies $we get $k$ leaves from them $\implies $we need $n-k$ more leaves. We need not consider "those" $T_i$s anymore. Finally, every tree has at least leaf, and $T$ has $n-k$ disjoint sub-trees, ( with $n(T_i)>1 )$ $\implies T$ has at least $(n-k)+k=n$ leaves!

Answer 2

Let $v_i$ be the degrees of the vertices and suppose the graph has $v$ nodes.

Notice $\sum\limits_{i=1}^v (v_i-1) = v-2$

Without loss of generality $v_1=n$

This means $\sum\limits_{i=2}^v (v_i-1) = v-n-1$

So at least $n$ of the summands are equal to $0$.