Let P= (u=v0, v1,..., vk), k equal to 1, be a u-v geodesic in a connect graph G. Prove that d(u,vi) = i for each integer i with 1

Question

Let P= (u=v0, v1,..., vk), k > equal to 1, be a u-v geodesic in a connect graph G. Prove that d(u,vi) = i for each integer i with 1<or equal to i < or equal to k.

we have been told prove by induction or contradiction are two good ways.

ganeshie8 · Answer

this may help http://www2.fiu.edu/~ritterd/notes/graph/fall2004/pro1-16.pdf

sswann222 · Answer

thank you! that definitely helps. I appreciate you typing it in a way i could easily follow.  :)

ganeshie8 · Answer

hey thats not my work, was looking for definitions and found that page. sorry im not really good in graph theory... i have just started these

sswann222 · Answer

looking through it i am getting lost in some of the notation.

\[Proof. It suffices \to show that if P, as \above, is a u - v path, and if d(u,v j ) = j fails for some integer j with 1 ≤ j ≤ k, then P is \not a u - v geodesic. Thus, suppose there is an integer j with 1 ≤ j ≤ k and d(u,v j ) ≠ j. Plainly, v 0 is adjacent \to v 1 . Consequently, d(v 0 ,v 1 ) = 1. Thus, 1 < j ≤ k

sswann222 · Answer

oh okay well either way it has helped me have a picture to work with. Thank you for at least pointing me in the right direction

ganeshie8 · Answer

its fine :) we may discuss if u have time, i hav understood the proof a bit

sswann222 · Answer

i have plenty of time. the last section where d(v 0, v 1) = 1.
it then says "Thus , 1< i < or equal to k"...how is that possible when it is showing it equal to 1?

ganeshie8 · Answer

let me think