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
  \      /   
   \    /
    \  /

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

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

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$.

  • $\begingroup$ How does "$d(u,v)=k$" follow from "the length of path $P$ from $u$ to $v$ is the diameter of $G$"? $\endgroup$ – bof Sep 10 '16 at 6:54
  • $\begingroup$ @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. $\endgroup$ – benguin Sep 10 '16 at 7:08
  • $\begingroup$ 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. $\endgroup$ – 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.$


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.