4
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ What is $\delta(G)$? Is it the minimum degree $\min_{v\in G} \deg(v)$? $\endgroup$
    – AlexR
    Oct 6 '14 at 7:34
  • $\begingroup$ $\delta(G)$ is the minimum degree of graph $G$. Thanks, I'll tidy that up so clarity is achieved. $\endgroup$
    – Old mate
    Oct 6 '14 at 7:35
  • 3
    $\begingroup$ Your proof looks good. $\endgroup$
    – Paul
    Oct 6 '14 at 7:36
  • $\begingroup$ That's good to hear. I was worried there'd be a hole in my logic or something I overlooked. Thank you both. $\endgroup$
    – Old mate
    Oct 6 '14 at 7:37
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Raoul
    Oct 6 '14 at 8:31
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Very nice. Thanks heaps, all! $\endgroup$
    – Old mate
    Oct 6 '14 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.