Bài tập 10, § 2

Cho $G$ là một đồ thị liên thông mà tập hợp các đỉnh là S. Với $x, y\in S$, đặt

$d_G(x, y) =$ inf$\{\ell \in \mathbf{N}:$ tồn tại một đường đi độ dài $\ell$ nối $x$ với $y\}$.

(a) Chứng minh rằng $d_G$ là một khoảng cách trên tập hợp S.

(b) Cho $G_1$ và $G_2$ là các đồ thị và $\varphi : G_1\rightarrow G_2$ là một cấu xạ đồ thị. Chứng minh rằng $d_{G_2}(\varphi (x), \varphi (y))\leqslant d_{G_1}(x, y)$ với mọi cặp $(x, y)$ các đỉnh của $G_1$.