Exercice 10, § 2

Soit G un graphe connexe dont S est l’ensemble des sommets. Pour $x, y\in S$, on pose

$d_G(x, y) =$ inf$\{\ell \in \mathbf{N}:$ il existe un chemin de longueur $\ell$ reliant $x$ à $y\}$.

a) Démontrer que $d_G$ est une distance sur l’ensemble S.

b) Soient $G_1$ et $G_2$ des graphes et $\varphi : G_1\rightarrow G_2$ un morphisme de graphes. Montrer que $d_{G_2}(\varphi (x), \varphi (y))\leqslant d_{G_1}(x, y)$ pour tout couple $(x, y)$ de sommets de $G_1$.