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.
