How can we prove this proposition :
Every graph G contains a path of length $ \delta(G)$ and a cycle of length at least $ \delta(G) + 1$, provided that $\delta(G) \geq 2 $.
($ \delta(G)$ is the minimum degree of G.)
Also, why does a graph which has a large minimum degree, contain long paths and cycles?
Best Answer
Here's a more transparent argument. (I think this is the proof you see in most introductory graph theory classes.)
Let $v_0,v_1,\ldots,v_k$ be the longest path in $G$. Then all the neighbors of $v_k$ lie on the path (otherwise we could extend the path; but the path is the longest by assumption). This means that $k\ge \deg v_k\ge \delta(G)$, thus the longest path in $G$ has length at least $\delta(G)$.
Now among the neighbors of $v_k$, which are all on the path, take the one that appears the first on the path, i.e., the $v_i$ with the minimum $i$. The cycle $v_i,v_{i+1},\ldots,v_k,v_{i}$ is clearly of length at least $\delta(G)+1$.