0
$\begingroup$

In a proof 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:

enter image description here

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – John Cataldo Feb 15 at 10:56
  • $\begingroup$ 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.) $\endgroup$ – PkT Feb 15 at 10:57
  • $\begingroup$ 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 $\endgroup$ – John Cataldo Feb 15 at 11:58
  • $\begingroup$ 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). $\endgroup$ – PkT Feb 15 at 12:02

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.