Let G be a graph with $\delta(G) \geq 2$. Questions regarding circumference Let G be a graph with $\delta(G) \geq 2$. Prove that the circumfrence $c(G)$ of $G$ satisfies $c(G)\geq \delta(G) + 1$
initial thoughts:
All I can basically say is that all the vertices are connected to two others. This inevitably will lead to a cycle because if you connect every vertex to two vertices, you will eventually be forced to connect to an already connected vertex, leading to a cycle. But I can't figure out why we can guarantee δ(G)+1
 A: Let's use your and Arthur's ideas. We start with a vertex $v_1$, choose a vertex from its neighborhood. Then we choose a vertex from $v_2$'s neighborhood, that is not $v_1$ to be $v_3$. We continue in this way choosing $v_{k+1}$ to be a vertex in the neighborhood of $v_k$ that is none of $v_1, \dots, v_{k-1}$.
This process must eventually stop (why?). Let $v_k$ be the last vertex in this process. We can't choose a $v_{k+1}$ because all the neighbors of $v_k$ must be in $\{v_1, \dots, v_{k-1}\}$. We know $v_k$ has at least $\delta(G)$ neighbors, so can we find a cycle including $v_k$ of length $\delta(G)+1$?

 Let $m$ be the smallest $i$ such that $v_{k}$ is adjacent to $v_i$. The cycle $v_m, \dots, v_k$ has length at least $\delta(G)+1$. (Justify this claim further.)

Also think about this: where in this proof have we used that $\delta(G) \geq 2$?
A: 
Note: By definition the circumference of $G$, denoted $c(G)$, is the longest cycle among all cycles in $G$.

Assuming that graph $G$ has $\delta(G) \geq 2$. Now, consider the longest path $P_{k}$; that is $P_{k}$ is the longest path on $k$-vertices. 
Therefore: $P_{k}: w_{1}-w_{2}-w_{3}-\cdots -w_{k-1}-w_{k}$. Then, clearly $w_{k}$ has all its neighbours present in $P_{k}$ (If not, then $P_{k}$ is not the longest path, as we can move to the $w_{k+1}$ adjacent to $w_{k}$). 
Hence, $|N(w_{k})| \geq \delta(G)$; that is there is a vertex $w_{j}$ for $1 \leq j \leq k$ on $P_{k}$ such that $d(w_{k}, w_{j}) \geq \delta(G)$ and $w_{k}w{j} \in E(G)$ . Since, $|N(w_{k})| = deg(w_{k})$, we then have $deg(w_{k}) \geq \delta(G)$. Clearly, $deg(w_{k}) \leq k - 1$.
As such, $k-1 \geq deg(w_{k}) \geq \delta(G) \Rightarrow k \geq deg(w_{k}) + 1 \geq \delta(G) + 1$. Notice that, $deg(w_{k}) + 1$ is a cycle, and the largest of such cycles is the circumference of $G$; that is $c(G) \geq deg(w_{k}) + 1 \geq \delta(G) + 1$, and our result follows. $\square$
Notice, that in our proof above we have also shown that graph $G$ has a path of length $\delta(G)$. Since, we can move from vertex $w_{k}$ to a vertex on $P_{k}$ that is at a distance $\delta(G)$ from $w_{k}$.
