0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David May 16 at 1:49
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.