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?