Proof in graph theory: maximum degree and number of leaves.

The case $k=1$ is trivial. Assume that $k \ge 2$. Let $u$ be a vertex of degree $k$ - So $u$ is not a leaf.

It is well known that $$\sum_{v \in V} \deg v = 2E$$ in every graph. Also, $$E=V-1$$ in every tree. Thus $$\sum_{v \in V} \deg v = 2V - 2$$ Define $L$ to be the set of leaves of the graph. The degree of every non-leaf vertex is at least $2$, so it follows that (with some abuse of notation)

$$\sum_{v \in V} \deg v = \deg u + \sum_{v \in L} \deg v + \sum_{v \in V\backslash(L \cup \{u\})} \deg v \ge k + L + 2(V-L-1)$$

Thus

$$2V -2 \ge k + 2V -L -2$$

and it follows that $L \ge k$.


Your intuitive reason is quite correct. One way to formalise this would be to take, for each neighbour of $v$, the longest path that starts at $v$ and passes through that neighbour. Each such path must end at a leaf, since if the last edge leads to a vertex of degree more than $1$ we could take another edge out of that vertex, which can't be part of a cycle so creates a longer path. All the $k$ leaves found in this manner are different: paths out of $v$ in different directions can't have the same end, since that would require a cycle.


If $v$ is a vertex of degree $k$ in the tree $T,$ then $T-v$ is a forest of $k$ trees $T_1,\dots,T_k,$ one for each neighbor of $v$ in $T.$ If $T_i$ consists of a single vertex, then that vertex was a leaf in $T.$ If $T_i$ contains more than one vertex, then $T_i$ has at least two leaves; at least one of them was not a neighbor of $v,$ so it was also a leaf in $T.$