# Prove that the degree of 2 vertices, which are the start and end of the longest path in a graph, are less than or equal to the length of the path

Let $$G$$ be a graph, and $$P$$ be the longest path in $$G$$. Let $$x$$ and $$y$$ be the start and end vertices of $$P$$ and let $$m$$ be the length of $$P$$. Prove that $$deg(x)\le m$$ and $$deg(y)\le m$$ for any graph $$G$$.

I can see why this is the case, but I am having trouble writing a proof for this. I am currently attempting this with proof by contradiction but am having trouble coming up with a generic way to show this.

How could I word this proof?

• If you "can see why this is the case", start by writing down what exactly makes you see this. That could be the beginning of a proof. – David May 16 at 1:49

How many neighbors of $$x$$ can be on the path $$P$$? Show that if $$\text{deg}(x)>m$$, then you can lengthen the path $$P$$ to include one more edge, which is a contradiction.
If the terminal vertices $$x,y$$ are adjacent to some vertex not in the path $$P$$, it can be extended by including that neighbour vertex. But since $$P$$ is the longest path, it can't be extended. Hence $$x$$ and $$y$$ are only adjacent to vertices already included in $$P$$. We have $$m$$ vertices in the path other than $$x$$, thus $$\deg(x)\le m$$. Similarly for $$y$$.
Note that this statement is true only for simple graphs $$G$$. Can you reason why?