Given $P = \{v_0, v_1, \cdots, v_n\} $ be a longest path in tree $T$. Show that the degree of $v_0$ and $v_n$ is 1.
My attempt: I have drawn a tree and simulate some paths so I know which one is the longest. But, once I see the other paths, I learn that the initial and terminal vertices also have the degree of 1. Every vertex in that same position must be 1. But, why it doesn't go logic to the problem? Now, what should I do?
Let's try to prove that there are exactly two vertices in $P$ such that those vertices have degree $1$. If we prove that, obviously, these vertices will be $v_0$ and $v_n$. And this will give us even more general result.
Suppose for a contradiction, there are more than two vertices such that degree of those vertices are $1$ in $P$. Then, by definition of path, all of those vertices must be either start or terminal vertices, which is a contradiction because a path in a tree has only one start and one terminal vertex (since it cannot be a circuit).
Now, suppose for a contradiction, there are less than two vertices with degree $1$ in the path. Since it is a tree, it cannot be zero because if it was zero, we would have a cycle. If the number of vertices with degree $1$ is one, then this is contradicting the assumption that $P$ is the longest path because the vertex with degree $1$ is $v_0$ and if there is no other vertex with degree $1$, then $d(v_n) > 1$ so it is not terminal at all. Therefore, there must be exactly two vertices with degree $1$ in longest path in tree and those are $v_0$ and $v_n$, obviously.
Short answer: If your path ends in a vertex connected to another edge, then you can add this edge and you path is longer than before.
More technical answer:
We have the longest Path $P=v_1,...,v_n$. Let's suppose: $d(v_n) > 1$.
Then there is a vertex $v_{n+1}$ and the edge $e = (v_n, v_{n+1})$ that is not part of the Path $P$. Otherwise we would have a circle in the tree. The Path $v_1,...,v_n,v_{n+1}$ is longer than $P$.
Contradiction!
Hence, $d(v_n) = 1$.
The same applies to $d(v_1)>1$.
