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?
Best Answer
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.