Let $T$ be a tree with $n$ vertices and with a vertex of degree $k$. Prove that the longest path in $T$ has at most $n – k + 1$ edges.
I'm unsure of how best to prove this. I know a tree has $n-1$ edges. Would I look at the vertex of minimum degree in order to maximise $n-k+1$? I feel like I'm missing something completely obvious!
Best Answer
Hint. Let $v$ be the vertex of $T$ with degree $k$. How many of the edges incident on $v$ cannot be involved in the longest path if $v$ is included in that longest path? How many of those edges cannot be involved if $v$ is not included?
Account for the fact that $T$ has (as you say) $n-1$ edges in all, and conclude that...