# Prove that if $\delta(G) \geq 2$ then $G$ contain a cycle

Prove that if $\delta(G) \geq 2$ then $G$ contain a cycle

I tried to prove this using proof by contrapositive.

I assume that $G$ has no cycle and show that $\delta(g) <2$.

The smallest cycle we can have is $C_3$. if $G$ has no cycle that mean $G$ has at least one vertex of degree $1$ or $0$. Meaning $\delta (G) <2$.

Is this proof sound acceptable? It look a little bit too short to me.

• I'm not sure what definitions/results you are using, but a graph with no cycles is a forest, and all forests contain vertices of degree 0 or 1 (leaves). If you already have some results on trees/forests that might be an easier way to go. Sep 15, 2014 at 21:33
• I wish I could use that. That sound alot simplier and make a lot of sense to me. But I haven't get that yet, not until I finish the next chapter. For now, all I can use is connected graph and everything before that. Sep 15, 2014 at 21:38

I doubt if what you have presented can be called a proof. We can discuss that in the comments.

For a proof choose a maximal path $P$ in the graph. (I am assuming the graph is finite.) Let $v$ be an end point of $P$. Now since $\delta(G)\geq 2$, there is an edge $e=vx$ incident to $v$ such that $e\notin E(P)$.

But since $P$ was a maximal path, the vertex $x$ must be in $P$ giving a cycle.

If every vertex has degree at least $2$, then depth-first search can always proceed until it finds a vertex that is active. The active vertices at that moment form a cycle.

Case $1$: "$G$ is connected" Assume that $G$ does not contain a cycle. Then $G$ is a tree. We know that every tree contains at least $2$ leaves, that is, vertices of degree $1$. However, this is a contradiction since $\delta(G)\geq2$. Thus $G$ contains a cycle.

Case $2$: " $G$ is disconnected" Assume that $G$ does not contain a cycle. Then $G$ is a forest and each component of $G$ is a tree. Since each component of $G$ is a tree we know that each component has at least $2$ leaves, that is, vertices of degree $1$. However, this is a contradiction since $\delta(G)\geq2$. Thus $G$ contains a cycle.

Hint: start from a generic vertex $v$. Its degree is positive, so there is some neighbor $w$ which has another neighbor other than $v$. We keep going along this path finding new vertices. Then we reach some vertex, say $z$, which doesn't have a new neighbor. But it's degree is at least two. What does that tell us?