For any two vertices $u$ and $v$ connected by a path in a graph $G$,
we define the distance between $u$ and $v$, denoted by $d(u,v)$, to be the length
of a shortest $u-v$ path. If there is no path connecting $u$ and $v$ we define
$d(u,v)$ to be infitnite.
Prove that if $d(u,v)$ $\geq$ 2, then there is a vertex $z$ in G such that
$d(u,v) = d(u,z)+d(z,v)$.
I tried to prove it by contradiction. The following is my incomplete work.
Suppose that $d(u,v)\geq2$ and there is no vertex $z$ in G such that $d(u,v)= d(u,z)+d(z,v)$.
Case 1: $d(u,v)=2$
Since there is no such vertex $z$, then the $W$ path from $u-v$ would be
$W$ = $u$e1e2$v$, which is a contradiction since by definition, the terms of a walk should be alternate vertices and edges.
I have no idea how to start with the second case, which is when $d(u,v)>2$. Please help.
Best Answer
I would approach this directly as follows:
Pick two vertices $u, v \in G$ such that $d_{G}(u, v) \geq 2$. Then we have the two following cases:
$\textbf{Case 1}$: $G = P_{n}$, then $u=x_{j} - x_{j+1} - \cdots - x_{k}=v$ where $1 \leq j \leq k \leq n$. We can pick any vertex on the path $u-v$ and label it as $x_{l}=z$ where $j < l < k$, and we achieve $d_{G}(u, v) = d_{G}(u, z) + d_{G}(z, v)$.
$\textbf{Case 2}$: Let G be some arbitrary graph. Let a path $P:u-v$ such that $d_{G}(u, v) \geq 2$. Now assume there exists another path $Q:u-v$ that is internally disjoint to the path $P$, then the path $Q$ must have the same length as path $P$. Since if it was shorter, then we would contradict the definition of $d_{G}(u, v)$. From this we again attain $d_{G}(u, v) = d_{G}(u, z) + d_{G}(z, v)$.