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?
On
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?
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.