Suppose G is a simple graph and δ>=2.Prove G has a cycle with at least δ+1 vertices Suppose $G$ is a simple graph and $\delta \ge 2$. Prove G has a cycle with at least $\delta+1$ vertices
This is all I think about this problem:
Consider the longest path in the graph. for example P: $v_0$
$e_1$ $v_1$ ... $e_k$ $v_k$ then we shoud talk about neighbor vertices of the $v_k$
.
But I dont know what can I say and how to solve it!
 A: Consider the longest path in G. Let this longest path $P$ be denoted by the vertices $P := v_1, v_2, \ldots, v_k$. Suppose that $v_k$ had a neighbor $w$ that was not in the set $S = \{v_1, v_2, \ldots, v_{k-1}\}$. This is a contradiction because then the path $v_1, v_2, \ldots, v_k, w$ would be longer than $P$. This tells us that $v_k$ only has neighbors in $S$. Now start walking along the path $P$ from $v_1$ to $v_k$, and stop at the first vertex $v_i$ for which there is an edge $(v_i, v_k)$ in the graph G. We know such a vertex must exist since $\delta$ is at least two and $v_k$ has all its incident edges in the set $S$. Consider the cycle $C := v_i, v_{i + 1}, \ldots, v_k, v_i$. Since $v_k$ didn't have any edges to the vertices $v_1, v_2, \ldots, v_{i-1}$ this means that $v_k$ must only have neighbors in the smaller set $S' = \{v_i, v_{i + 1}, \ldots, v_{k-1}\}$. If $\delta$ were bigger than the number of vertices in this set $S'$, there would be no way that $v_k$ could have at least $\delta$ edges incident, which is required. In other words, $\delta \leq |S'| = k - i$. Note that the cycle $C$ has exactly $k - i + 1$ edges, so $\delta + 1 \leq k - i + 1 = length(C)$.
A: Let $P = v_1,\ldots, v_k$ be a longest path in $G$ and suppose $\delta(G)\ge 2=\delta$. Then there are at least $\delta-1$ edges from $v_k$ incident with vertices $W=\{v_1,\ldots, v_{k-2}\}$.
Let $U=\{v_1,\ldots,v_{k-\delta}\}$ and $V=\{v_{k-\delta+1},\ldots, v_{k-2}\}$ and observe that $U\cup V=W$ and $|V|=\delta-2$. So there must be at least 1 edge from $v_k$ that connects to $U$, say $v_i$. Then $C$, the cycle starting at $v_i$ along $P$, will include at least the vertices $v_i$, all the vertices of $V$, $v_{k-1}$ and $v_k$. That is to say $C$ will have at least $\delta+1$ vertices.
