# Path and cycle length proof

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?

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$.
• Well, $k=8$ means the graph will be quite large as every vertex needs at least $8$ neighbors (and one vertex needs exactly $8$ neighbors), in fact, $K_9$ is the smallest example. – blazs Jun 26 '15 at 11:31
Lets consider the longest path $l$. We define $v$ to be the last point on $l$. If $l$ is the longest path then $v$ is not connected with any vertex $u$ which is not on $l$. But $v$ has a degree at least $\delta(G)$ and $l$ must contain at least $\delta(G)$ vetices.
The same logic is true for cycles: the same vertex $v$ is connected only with vertices lying on $l$ and the farthest vertex from $v$ forms a cycle of length at least $\delta(G)+1$.