[Math] Prove every graph $G$ has a path with $\delta(G)$ edges.

graph theoryproof-verification

I'm relatively new to Graph Theory, so please be gentle.

Here's what I have. Any feedback on how I could improve and finalise my little proof would be amazing. Otherwise, if it is a sound proof, let me know! Thanks for your time, all.

Every graph $G$ has a path with $\delta(G)$ edges.

$\mathbf{Proof.}$ Let $L$ be the longest possible path in $G$ and assume that $|L|<\delta(G)$. Consider vertex $v$, an endpoint of $L$. The vertex $v$ will have at least $\delta(G)$ vertices in its neighbourhood. As $L$ is the longest path in $G$, all vertices in $N_G(v)$ will be elements of path $L$'s vertex set. But this is a contradiction, as $L$ has at least $\delta(G)+1$ vertices, and so also contains at least $[\delta(G)+1]-1=\delta(G)$ edges. So $|L|\geq\delta(G)$, as was to be shown.

Best Answer

Remove the 'Proof by contradiction' part and you have a direct proof.

Take any vertex $v_1$. It has at least degree $\delta$. Take one of the $\delta$ edges to $v_2$. Remove $v_1$ from $G$. Remaining graph has degree at least $\delta - 1$. Repeat.