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.

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$
