# Prove every graph $G$ has a path with $\delta(G)$ edges.

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.

• What is $\delta(G)$? Is it the minimum degree $\min_{v\in G} \deg(v)$? Oct 6, 2014 at 7:34
• $\delta(G)$ is the minimum degree of graph $G$. Thanks, I'll tidy that up so clarity is achieved. Oct 6, 2014 at 7:35
• I'm used to seeing $|L|$ used to mean the number of vertices of $L$ (this is how it's used in Diestel for example) rather than the number of edges. If you've encountered it, notation like $|E(L)|$ or $e(L)$ might be less ambiguous. (Though obviously if you're doing some sort of course then stick to the suggested notation.) Oct 6, 2014 at 8:31
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.