3
$\begingroup$

I'm reading up on graph theory using Diestel's book. Right on the outset I got confused though over proposition 1.3.1 on page 8 which reads:

Proposition 1.3.1. Every graph G contains a path of length $\delta(G)$ and a cycle of length at least $\delta(G)+1$ (provided that $\delta(G) \ge 2$).

Following the proof I can see why this would be true if G actually contains a cycle, but I keep thinking there are many graphs, like the path graph itself and connected trees, with $\delta(G) \ge 2$ but which don't have any cycles. I found this question on the same proposition, asking to prove it. The accepted answers there seem to quote Diestel's proof verbatim, assuming G just has a cycle.

I'm pretty sure I'm missing something, so I wonder why one would choose this formulation or whether I'm simply misunderstanding the proposition. Is it assumed that graphs are cyclic unless stated otherwise? Might this be specific to the context in a way I managed to overlook?

As a reminder, $\delta(G)$ is the minimum degree, taken over all vertices of $G$.

$\endgroup$
4
$\begingroup$

If $\delta(G) \geq 2$ every vertex is connected to at least 2 others. This invariably leads to a cycle in any finite graph.

To see why, try to construct a path without a cycle from a graph with $\delta(G) \geq 2$. Every vertex you add is connected to either a previously added vertex (forming a cycle), or an other vertex. However, in turn, that vertex is connected... Since the graph is finite you will at some point run out of vertices to add which you haven't seen already, forcing you to form a cycle.

$\endgroup$
  • $\begingroup$ The same argument shows the claim for $\delta \geq 2$ and cycles of length $\delta + 1$, you just have to observe that the "last vertex" on the path has to connect to at least $\delta$ vertices on the path. $\endgroup$ – G. Bach Sep 17 '15 at 9:08
  • $\begingroup$ Ah right, every vertex... I'm being dense, thanks! $\endgroup$ – Fasermaler Sep 17 '15 at 10:08
1
$\begingroup$

A path is a tree; trees have minimum degree $1$ so do not meet the hypothesis of the proposition. Conversely, if a graph has minimum degree at least $2$, then it is not a tree, so it does contain a cycle.

$\endgroup$
  • $\begingroup$ This proof is not complete. You seem to be abusing the contrapositive: "A path has min-degree $1$, so if it has min-degree greater than $1$ it has a cycle." This implies that every graph is either a path or contains a cycle. $\endgroup$ – Kittsil Sep 17 '15 at 7:30
  • 2
    $\begingroup$ @Kittsil He did say "tree", not "path", and for trees the statement is true (if we restrict ourselves to connected graphs, which we can do wlog): every connected graph is either a tree or has a cycle. $\endgroup$ – G. Bach Sep 17 '15 at 9:10
  • $\begingroup$ @G. Bach Of course the statement is true. But it needs to be proved here; currently, this is begging the question. $\endgroup$ – Kittsil Sep 17 '15 at 12:23
  • $\begingroup$ @Kittsil Well we almost always have a degree of informality even in what is considered rigorous proofs (I remember once seeing an actually rigorous proof of something basic, and it filled a whole book - I think it was by Hilbert, but I can't find it), and I think David's answer is not too "handwavy". $\endgroup$ – G. Bach Sep 17 '15 at 12:46
  • $\begingroup$ @Kittsil I'm not begging the question or abusing the contrapositive. We can assume the graph is connected: work component-by-component, if not. Every tree has $\delta=1$, so every graph that has $\delta=2$ is not a tree. Trees are, by definition exactly the connected acyclic graphs, so any connected graph that is not a tree has a cycle. $\endgroup$ – David Richerby Sep 17 '15 at 20:58

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.