# Longest path technique of proving a graph theory problem

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?

• Doesent $u$ need to be the an end vertex on the path? – Paddling Ghost Aug 3 '15 at 15:48
• 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. – Paddling Ghost Aug 3 '15 at 18:45

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.