# Prove that any sub-path of longest path in directed graph is longest path too

I need to prove/disprove an claim that related to "The longest path problem".

For given directed graph $G(V,E)$ with non negative weight function $w(u,v)$, define $L'(u,v)$ as longest path from $u$ to $v$.

I need prove/disprove that for any given simple path $P(v_1,v_2,\ldots,v_i,\ldots,v_j,\ldots,v_k)$ sub-path $(v_i, v_{i+1}, v_{i+2},\ldots,v_j)$ where $1\le i<j\le k$ is longest simple path from $v_i$ to $v_j$.

In simple words, are the sub-paths of Longest path, are longest path?

What I tried is:

Define path $P(v,\ldots,w,\ldots,z,\ldots,v)$

The longest path is $L'(u,v) = L'(u,w) + L'(w,z) + L'(z,v)$

If $L'(w,z)$ is not the longest path, this means that $L'(u,v)$ is not longest path from $u$ to $v$ $\Longrightarrow$ $L'(w,z)$ is longest path from $w$ to $z$.

Is it corrent prove? I know that for undirected graph this prove is wrong and I have an counterexample.

Thanks.

• Couldn't $L'(u,w)+L'(w,z)+L'(z,v)$ fail to be a path? – Hagen von Eitzen Jun 7 '14 at 12:02

For simplicity, lets make all weights equal. Now, if you take two consecutive vertices on this longest path, isn't it possible there is a longer path between those two, which cannot be combined with the original longest path?

Here is an example:

$$1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8$$ Add the following arcs: $6 ->9 ->1 -> 10 -> 7$

Which is the longest path? Which is the longest path from $6$ to $7$?

• Even simpler is a triangle. As an undirected graph the longest path between two vertices is length two, despite the sub-path between two adjacent vertices of that path having length one. These undirected counterexamples can be converted to directed ones by replacing each undirected edge with two oppositely directed edges. – hardmath Jun 7 '14 at 12:19
• @hardmath The problem is about directed graphs ;) And if you make the triangle directed, is not a counterexample anymore. – N. S. Jun 7 '14 at 12:24
• By most definitions a path visits a vertex only once, so by adding directed edges among all possible pairs of three vertices, a longest directed path will have length two. But as with the undirected case, any "sub-path" between two adjacent vertices of a path is not "longest". – hardmath Jun 7 '14 at 12:27
• I thought it worth mentioning because the OP is aware of undirected counterexamples. – hardmath Jun 7 '14 at 12:30
• L'(1,8) = 1->2->3->4->5->6->7->8 Sub path P(6,7) = 6->7 But the is exists L'(6,7) = 6->9->1->10->7 Thank you N. S. :) – Alexander R. Jun 7 '14 at 12:35