Question: Let G be a simple graph, where the minimum degree of a vertex is k. Show that G contains a path of length at least k and a cycle of length at least k + 1.

Proof: Consider the longest path P in G. Let u be an point of P. By assumption of P being the longest path, all neighbors of u are in P . Since u has at least k neighbors (minimum 3 degree in G is k), the path P has at least k + 1 distinct vertices and so its length is at least k.

I'm trying to understand why considering the longest path method works. I'm trying to understand why they say if you have the longest path, then a vertex u will have all the neighbours in P. I can see the argument, that if not all the neighbours of u are in P, then you can make a longer path by extending P with that neighbour, which makes our assumption of the longest path wrong.

But, what if you have a vertex like, pretend your palm is a vertex, and that vertex has 5 neighbours (our 5 fingers). A path including the palm vertex can't visit all 5 fingers, otherwise it has to repeat some edges. What am I missing in my understanding?

  • $\begingroup$ Doesent $u$ need to be the an end vertex on the path? $\endgroup$ – Paddling Ghost Aug 3 '15 at 15:48
  • $\begingroup$ By the way, your counter example works. That is, consider $K_{1,5} $ which is the name of your "hand" graph. A path of maximum length is of length 2, but not all of the central vertex's neighbors are included in the path. $\endgroup$ – Paddling Ghost Aug 3 '15 at 18:45

It is not generally true of a path of maximum length that all of any vertices neighbors need be included in the path. For a counter example, consider a path of maximum length on a caterpillar.

What is true of a path of maximum length in any graph: both of the end vertices of the path have their neighbors completely in the path.

Assume otherwise, that an end vertex $u$ has some neighbor not on the path, say $v$, then the original path plus the edge $uv$ is a path of greater length.

Hopefully this clears up your understanding. I would go back to the proof you were quoting and make sure that $u$ is an end vertex. If not, then the proof has a problem.

  • 1
    $\begingroup$ Thank you! This makes a lot more sense knowing that it has to be the end vertex. The proof had a problem as what I wrote in my question was a copy and paste. $\endgroup$ – user3240815 Aug 3 '15 at 18:52
  • $\begingroup$ If you found my answer helpful and satisfactory there is a little green check mark next to my answer that you can select to mark it as the answer. ;) $\endgroup$ – Paddling Ghost Aug 4 '15 at 2:01

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.