Exercise 10, § 2

Let $G$ be a connected graph whose set of vertices is S. For $x, y\in S$, one sets

$d_G(x, y) =$ inf$\{\ell \in \mathbf{N}:$ there exists a path of length $\ell$ joining $x$ to $y\}$.

(a) Prove that $d_G$ is a distance on the set S.

(b) Let $G_1$ and $G_2$ be graphs and $\varphi : G_1\rightarrow G_2$ a graph morphism. Prove that $d_{G_2}(\varphi (x), \varphi (y))\leqslant d_{G_1}(x, y)$ for every pair $(x, y)$ of vertices of $G_1$.