Let $G$ be a connected graph such that the length of a longest path in $G$ is $\ell$

I was able to prove that if two longest paths of length $\ell$ exist then they must share a vertex now i am asked the following.

Prove that if $P,Q $ are two paths of length $\ell$ that intersect in a single vertex, then $\ell$ is even.

this seems fairly obvious the vertex that they share must split them exactly in half if it didn't then the shared path to that vertex down one then up the other would be a longer path than both $P$ and $Q$ but I'm not sure how to prove it.

  • $\begingroup$ What you've said is the proof. You can "dress it up more nicely" but the core argument is there. I'd add notation: say that the vertices of one path are $P_0, \dots, P_\ell$, of the other $Q_0, \dots, Q_\ell$, and the shared vertex is $P_i = Q_j$. Then you can write down the path "up one and down the other" explicitly and find its length in terms of $i$ and $j$. $\endgroup$ Sep 15 '17 at 17:51
  • $\begingroup$ Sorry fairly new to graph theory so i get confused with what is a valid argument alot ill try and write it up better. $\endgroup$
    – Faust
    Sep 15 '17 at 17:56

Let $v_0v_1\ldots v_\ell$ and $w_0w_1\ldots w_\ell$ be the two distinct paths $P,Q$ of length$ l$ that intersect in a single vertex. By assumption, $v_n=w_m$ for some indices $n,m$ and all other vertices are distinct. Hence $v_0v_1\ldots v_nw_{m+1}w_{m+2}\ldots w_\ell$ and $w_0w_1\ldots w_mv_{n+1}v_{n+2}\ldots v_\ell$ are paths of length $n+\ell-m$ and $m+\ell-n$. As both numbers must be $\le \ell$, we conclude $n=m$. As we can replace $v_0v_1\ldots v_\ell$ with $v_\ell v_{\ell-1}\ldots v_0$ and thereby replace $n$ with $\ell-n$, we conclude that $\ell-n=m=n$, so $\ell=2n$.

  • $\begingroup$ I guess P and Q must share a vertex because if not then there would be a even longer path and P and Q are part of the longest path length l. $\endgroup$ Oct 8 '17 at 19:28

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.