1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Can you please provide an example, say by taking k = 8 ? $\endgroup$ – Ankit Panda Jun 26 '15 at 11:20
  • $\begingroup$ 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. $\endgroup$ – blazs Jun 26 '15 at 11:31
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.