Trees have a vertex of degree $1$ Prove that any tree has a vertex of degree $1$.
Let graph $G=(V,E)$ have $n$ vertices and $m$ edges where $m<n$. We need to prove that the minimum degree of, $\delta (G)=1$ 
Since G is connected then there exists a path from $u$ to $v$ such that $u,v \in V$. 
Is what I have said so far correct? I really don't know how to carry it on. I need a formal answer.
 A: In fact, you can say more. Any tree has at least 2 vertices of degree 1.
Proof: Since $G$ is a tree, $G$ is connected. Let $P=\{u=v_0,v_1,\ldots,v_{n-1},v_n=v\}$ be a $u-v$ path of maximum length. Clearly $u$ is adjacent to $v_1$ and $v$ is adjacent to $v_{n-1}$ so that $\deg(u)\ge1$ and $\deg(v)\ge 1$.
Now $u$ cannot be adjacent to any other vertices in $G$ not on $P$ because then we could extend $P$ to a longer path in $G$. Similarly $v$ cannot be adjacent to any other vertex in $G$ not on $P$. 
Neither $u$ nor $v$ can be adjacent to any other vertices in $P$ other than $v_1$ and $v_{n-1}$ because that would induce a cycle in $G$, which contradicts the assumption that $G$ is a tree.
Thus $\deg(u)=1$ and $\deg(v)=1$.
A: This is trivial: every tree has n-1 edges, where n is the number of vertices. If every vertices has degree at least 2 the sum of the degree is at least 2n.So there are at least n edges. Impossible.
A: How you make the argument will depend to some extent on what you already know about trees. One approach that uses nothing beyond the definition — a tree is a connected, acyclic graph — is to show that if $G$ has no vertex of degree $1$, then you can construct a cycle in $G$. Start at any vertex and keep moving to a new one as long as you can; there are only finitely many vertices altogether, so at some point ...
