Diameter of a path

252 Views Asked by At

Show that the diameter of the path of $k+1$ vertices (known as $P_k$) is $k$.

The following definitions are given:

A path of length $k$ in a graph $\Gamma$ is a graph map $\gamma : P_k \rightarrow \Gamma$.

For any two vertices $x$ and $y$ in $\Gamma$, the minimum length of a path between $x$ and $y$ is called the distance between $x$ and $y$.

$$\operatorname{diam}( \Gamma ) = \sup_{x,y \in V} d_\Gamma (x,y)$$

I'm just lost on what technique to use here.

1

There are 1 best solutions below

0
On BEST ANSWER

Hint: Label the vertices of $P_k$ as $v_1, v_2, \ldots, v_{k+1}$, where the only edges are $(v_i, v_{i+1})$ for $i = 1, 2, \ldots, k$. What is the length of the shortest path from $v_1$ to $v_{k+1}$? What other vertices must this path include? (Notice that if a path from $x$ to $y$ includes $u$ and $v$, then $d_\Gamma(u,v) \le d_\Gamma(x,y)$).