# Proving that if $\delta(G)=\min\limits_{v\in V}d(v)$, there exists a path of length $\delta(G)$: confusion about construction of path using neighbors

In a proof of this statement at some point we say that given $$v_0v_1\dots v_k$$, a path of maximum length, we can suppose that all neighbors of $$v_0$$ are in the path. I see how we can add one neighbor $$u$$ to the beginning of the path but if $$v$$ has more neighbors how does this work?

A similar argument is used in the second part... And I also don't understand how the second part proves the existence of a cycle of length $$\delta(G)+1$$. To me it only proves that there exists a cycle of length $$\ge\delta(G)+1$$

This graph has $$\delta=3$$ but it's not obvious why every neighbor of $$4$$ or $$2$$ is in the longest path: ## 1 Answer

You can use the fact that $$v_0, \dots, v_k$$ is the path of maximum length to prove the claim about $$v_0$$'s neighbors. The part where it says "Indeed, assuming that $$v_0$$ has another neighbor..." is what you're looking for.

As for the second part, the question is probably asking for a cycle of length $$\geq$$ $$\delta(G)+1$$. Otherwise, $$G=C_n$$ would be a counter-example for $$n > 3$$.

• Yeah but if $v_0$ has three neighbors $u$, $v$ and $v_1$ that aren't connected between themselves how do you add $u$ and $v$ to the path? – John Cataldo Feb 15 at 10:56
• Let's say that the path with maximum length has length $l$. The argument is that if there is any neighbor of $v_0$ which does not appear in the maximum-length path, one can add it to the beginning of the path. This new path will have a length of $l+1$, which is impossible. (You don't have to add both $u$ and $v$. One of them is enough.) – PkT Feb 15 at 10:57
• Consider the graph $V=\{v,v_1,v_2,v_3,w,w_1,w_2,w_3\},~E=\{vw,vv_1,vv_2,vv_3,ww_1,ww_2,ww_3\}$ the longest path has length $2$ and you cannot add all the neighbors of $v$ to it. Here $\delta=1$ so it's not really a contradiction but if we added the edges $v_1v_2,v_2v_3,w_1w_2,w_2w_3$ then $\delta = 2$ but the argument by itself is insufficient. We can only add $v_1,v_2,v_3$ because the edges $v_1v_2,v_2v_3,v_3v$ exist, which is not obvious – John Cataldo Feb 15 at 11:58
• The longest path has length 3 (e.g. $v_1, v, w, w_1$). In any case, $v_0$ in the statement was chosen to be an endpoint of the longest path, in this case, $v_1$ or $w_1$, all of whose neighbors are already in the path. ($v$ can never be an endpoint to a path of maximum length, so we don't care if all of its neighbors are not in the path of maximum length). – PkT Feb 15 at 12:02