# Proving cycles in graph

I have the problem: Let $d>1$ be an integer. Prove that if every vertex of a graph $G$ has degree at least d, then G contains a cycle of length at least $d + 1$.

I'm pretty sure this can be done by induction and the base case would be a connected graph of 3 vertices for which every vertex has degree 2 and G has a cycle of length 3. I don't really know where to go from here though.

I think it may have something to do with the fact that the graph with minimum degree $d+1$ would need $d+1$ edges added to the graph which satisfies the proposition for $d$, but I don't know how to take that further.

Take a maximal path $u_0\dots u_n$. Now, since the path is maximal $u_0$ has all of its neighbours inside the path, there are at least $r$ of these by hypothesis.
So at least $r$ elements of $u_1,u_2\dots u_n$ are neighbours of $u_0$, the last of these elements must be of the form $u_j$ with $j$ at least $n$.
The cycle $u_0,u_1,u_2,\dots u_j,u_0$ is the desired one.
Let $\delta(G)$ denote the smallest degree in a graph $G$. For a graph $G$, if $\delta(G)=d$, then $G$ contains a path of length $d$ and, furthermore, if $d>1$, then $G$ contains a cycle of length $d+1$.
Proof. Let $d\geq 1$ and suppose that $G$ is a graph with $\delta(G)=k$. Let $P$ be a longest path in $G$, between, say, $u$ and $v$. Since $P$ is maximal, every neighbor of $u$ is in $P$; since $u$ has at least $d$ neighbors, $P$ has at least $d$ vertices besides $u$, that is, $P$ has length at least $d$. If $d\geq 2$, the edge to the farthest neighbor of $u$ in $P$ completes a cycle of length at least $d+1$. $\blacksquare$