Proof in graph theory: maximum degree and number of leaves. I have to prove that if $v$ is a vertex of maximum degree in a tree and the degree of $v$ is $k$, then the tree has at least $k$ vertices of degree $1$.
I think I get why that is true: If $v$ has $k$ neighbors, then these may or may not have neighbors. If they are leaves, then we are done. If they do have neighbors, then eventually we will reach the leaves, since the tree is finite. So it is obvious that the tree has at least $k$ vertices of degree $1$. But how do I prove it formally?
 A: 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$.
A: 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.
A: 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.$
