[Solved]: Every graph with $delta(G) ge 2$ has a cycle of length at least $delta(G)+1$?

ignougroup
Problem Detail: 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$.

Asked By : Fasermaler

Answered By : orlp

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47258