# Let P be the longest path in G…

I'm having trouble figuring this problem out. I would like some help. This is the problem:

Let $P = ( u = v_0,v_1,v_2,.....v_k = v),k>=1$ be the longest path in $G$. Prove that $d(u,v_i) = i$ for each $i = 1,2,3,....k$

My first thought was say that exists a vertex $w$ which joins to $v$ and $v_i$, where $v_i$ belong to $P$, so exists $d(u,v_i)$ is different of $i$, something like:

  v       vi        v
o----...-o-......-o
\      /
\    /
\  /
o
w


so there is a path $T'= (w,u)\cup(u,P,v)$ and $|T'| = |P|+1$ which can't be because $P$ is the longest one but I'm not sure that is enough for proving it. I also thought what if there is a edge$(u,v_1), ( u,v_2),(u,v_3)$...etc? that would make $d(u,v_i)$ not $i$, I mean what if that happens and besides also exist edges: $(u,v_1), ( v_1, v_2), (v_2,v_3),...(v_{k-1},v_k)$

please help

• What is meant by$d(u,v)$. Is it the shortest path distance between $u$ and $v$? – Mayank Deora Sep 10 '16 at 1:51
• Welcome Math.SE! Take the tour to get familiar with this site. Mathematical expressions and equations can be formatted using $\LaTeX$ syntax. – Shailesh Sep 10 '16 at 1:52
• It appears that the statement is false, for a counterexample use any large complete graph. – Anon Sep 10 '16 at 1:59
• well, it also says something about that |P| = diam(G) – Daniela Velásquez Garzón Sep 10 '16 at 3:39
• yeah d(u,v) is the distance between u and v – Daniela Velásquez Garzón Sep 10 '16 at 3:44

## 2 Answers

Notice that since the length of path $P$ from $u$ to $v$ is the diameter of $G$, then $d(u,v) = k$, i.e., there does not exist a path from $u$ to $v$ whose length is less than $k$.

We know $P' = (u=v_0, v_1, \dots, v_i)$ is a path of length $i$ from $u$ to $v_i$ so $d(u,v_i) \leq i$. Now suppose that $d(u,v_i)=l$ where $l < i$. That means there exists a path $Q = (u = w_0, w_1, \dots, w_l = v_i)$ of length $l$. Using both of these paths, we construct a path from $u$ to $v$ as follows,

$$(u=w_0, w_1, \dots, w_l = v_i, v_{i+1}, \dots, v_k = v)$$

which is a path of length $l+(k-i) < i+(k-i) = k$. Thus, we have found a path from $u$ to $v$ whose length is less than $k$, a contradiction since $d(u,v) = k$. Thus, it must be the case that $d(u,v_i) \geq i$. Since $d(u, v_i) \leq i$ and $d(u,v_i) \geq i$, we conclude $d(u, v_i) = i$.

• How does "$d(u,v)=k$" follow from "the length of path $P$ from $u$ to $v$ is the diameter of $G$"? – bof Sep 10 '16 at 6:54
• @bof Good point. I haphazardly made the assumption that $P$ was some realization of $G$'s diameter, i.e., that $P$ was actually a $u-v$ geodesic. – benguin Sep 10 '16 at 7:08
• Perhaps the "real problem" assumes that $d(u,v)=k.$ But then there is no need to say anything about the diameter of the graph. – bof Sep 10 '16 at 7:12

The following seems to be a counterexample.

Let $G$ be the graph with vertices $v_0,v_1,v_2,v_3,v_4,x,y$ and edges $v_0v_1,v_1v_2,v_2v_3,v_3v_4,v_0v_2,v_2x,xy.$

The diameter of $G$ is $\operatorname{diam}(G)=d(v_4,y)=4.$

The path $P=(v_0,v_1,v_2,v_3,v_4)$ has $\operatorname{length}(P)=4=\operatorname{diam}(P),$ and it is a path of maximum length in $G,$ although of course there are other paths of length $4.$

However, $d(v_0,v_2)=1.$