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$.


2 Answers 2


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.

  • $\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, 2015 at 9:08
  • $\begingroup$ Ah right, every vertex... I'm being dense, thanks! $\endgroup$
    – Fasermaler
    Sep 17, 2015 at 10:08

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.

  • $\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, 2015 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, 2015 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, 2015 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, 2015 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$ Sep 17, 2015 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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