# Shortest Path Between Two Vertices Of A Graph.

graph theory

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.

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