Simple proof by contradiction in graph theory

Question

The question is as follows: Let P be the longest path in a simple graph G, and let $\lambda$ be the length of P. Show that both the starting point and ending point of P must have degree $\le\lambda$.

My proof: Let s be be the starting vertex of P. Assume deg(s) > $\lambda$. If s is connected to every other vertex in P, then deg(s) = $\lambda$ $thus far$. Since deg(s) > $\lambda$, it follows that s is connected to some vertices not in P. This implies s is not the starting vertex, which is a contradiction. If s is $not$ connected to every other vertex in P, then the deg(s) $<\lambda$ $thus far$. Again, this means s must be connected to some vertices outside P, which is a contradiction. Therefore deg(s) $\le\lambda$. The same argument holds for the end vertex of P.

My proof does not involve the fact that P is the longest path in G, which leads me to doubt its validity. I would like a verification of my proof.

EDIT: If my proof is valid, does that mean that the above result is true regardless of whether P is the longest path?

Answer 1

Your proof does use the assumption that $P$ is the longest path.

This implies s is not the starting vertex, which is a contradiction.

By this, what you mean is that $P$ can be extended, which contradicts the assumption that $P$ is the longest path.

By saying, "if not, s wouldn't be the starting vertex", you mean $P$ can be extended. If $P$ were the the longest path, then such an extension wouldn't have been possible. Suppose you drop the assumption '$P$ is the longest path'. Then what happens? For instance, take the graph $K_3$ and a $1-$length path $P$, which is an edge, say $e=\big \{ s,t \big \}$. Here, $deg(s) = 2$, but $\lambda =1$.

Answer 2

For a path $P$ of length $\lambda$, you are trying to prove:

If $P$ is a longest path in $G$, then the first and last vertices of $P$ have degree at most $\lambda$.

Your (correct) strategy here is to actually demonstrate the contrapositive statement:

If either the first or last vertex of $P$ has degree larger than $\lambda$, then $P$ is not a longest path in $G$.

But you are right that your proof is demonstrating something a bit more than required. The only property of $P$ being a longest path that you are using is that $P$ is not contained in any longer path. This property can be true for other paths, even if they are not of maximum length. So actually your proof is also a proof for the following.

If $P$ is a maximal path (i.e., $P$ is not contained in a longer path), then the first and last vertices of $P$ have degree at most $\lambda$.