Characterization of the geodesic distance on infinite graphs

Proof. It follows directly from (2) that the function $d_G$ is symmetric and, moreover, $d_G(u,v)=0$ holds iff $u=v$. Thus, by Definition 2.1, the function $d_G$ is a metric on $V(G)$ iff the triangle inequality $$\begin{array}{}\text{(3)}& d_G(u,v)⩽d_G(u,w)+d_G(w,v),\end{array}$$ holds for all $u,v,w\in V(G)$.

Inequality (3) is trivially valid if $u=v$, $u=w$, or $w=v$. Suppose that $u,v$ and $w$ are pairwise distinct.

Let us consider two paths $P_{u,w}\subseteq G$ and $P_{w,v}\subseteq G$ such that: $P_{u,w}$ connects $u$ and $w$; $P_{w,v}$ connects $w$ and $v$; $$\begin{array}{}\text{(4)}& d_G(u,w)=|E(P_{u,w})|,\end{array}$$ and $$\begin{array}{}\text{(5)}& d_G(w,v)=|E(P_{w,v})|.\end{array}$$

Write $$\begin{array}{}\text{(6)}& G_1:=P_{u,w}\cup P_{w,v}.\end{array}$$

Then $w\in V(P_{u,w})\cap V(P_{w,v})$ and, consequently, $G_1$ is a connected subgraph of $G$ by Lemma 2.4. It follows from (6) that $$u,v\in V(G_1).$$

Hence, the geodesic distance $d_{G_1}(u,v)$ is correctly defined, and, by Definition 2.5, the inequality $$\begin{array}{}\text{(7)}& d_G(u,v)⩽d_{G_1}(u,w),\end{array}$$ holds.

Inequality (7) implies that (3) holds if $$d_{G_1}(u,v)⩽d_G(u,w)+d_G(w,v).$$

Let $P_{u,v}^1$ be a path joining $u$ and $v$ in $G_1$ such that $$d_G(u,v)=|E(P_{u,v}^1)|.$$

It follows directly from the definition of paths that $$\begin{array}{}\text{(8)}& |E(P_{u,w})|=|V(P_{u,w})|-1,\end{array}$$ $$\begin{array}{}\text{(9)}& |E(P_{w,v})|=|V(P_{w,v})|-1,\end{array}$$ and $$\begin{array}{}\text{(10)}& |E(P_{u,v}^1)|=|V(P_{u,v}^1)|-1.\end{array}$$

Now, using (4)–(5), (6), and (8)–(9) we obtain $$\begin{array}{}\text{(11)}& \begin{array}{rl}{d}_G(u,w)+d_G(w,v)& =|V(P_{u,w})|+|V(P_{w,v})|-2\\ & =|V(G_1)|+|V(P_{u,w})\cap V(P_{w,v})|-2.\end{array}\end{array}$$

Since $w$ belongs to $V(P_{u,w})\cap V(P_{w,v})$, (11) implies $$\begin{array}{}\text{(12)}& d_G(u,w)+d_G(w,v)⩾|V(G_1)|-1.\end{array}$$

Similarly, it follows from $P_{u,v}^1\subseteq G_1$ and (10) that $$\begin{array}{}\text{(13)}& d_{G_1}(u,v)=|V(P_{u,v}^1)|-1⩽|V(G_1)|-1.\end{array}$$

Inequality (3) follows from (7), (12) and (13).

The proof is completed. 

Proof. $(i)\Rightarrow (ii)$. Let $G$ be a connected graph such that $(X,d)$ and $(V(G),d_G)$ are isometric. Then inclusion (14) follows from Definitions 2.2 and 2.5.

Let us consider arbitrary $x,z\in X$ such that $d(x,z)⩾2$. We need to show that there exists a point $y\in X$ such that $$\begin{array}{}\text{(15)}& x\ne y\ne z,\end{array}$$ and $$\begin{array}{}\text{(16)}& d(x,z)=d(x,y)+d(y,z).\end{array}$$

Let $\mathrm{\Phi }:X\to V(G)$ be an isometry between the metric spaces $(X,d)$ and $(V(G),d_G)$. Then the inequality $$\begin{array}{}\text{(17)}& d_G(\mathrm{\Phi }(x),\mathrm{\Phi }(z))⩾2,\end{array}$$ holds by Definition 2.2. Let $P$ be a path in $G$ joining $\mathrm{\Phi }(x)$ and $\mathrm{\Phi }(z)$ such that $$d_G(\mathrm{\Phi }(x),\mathrm{\Phi }(z))=|E(P)|.$$

Inequality (17) implies $|E(P)|⩾2$. Consequently, there is $w\in V(P)$ such that $$\begin{array}{}\text{(18)}& \mathrm{\Phi }(x)\ne w\ne \mathrm{\Phi }(z).\end{array}$$

Now, using Lemma 2.8 we obtain $$\begin{array}{}\text{(19)}& d_G(\mathrm{\Phi }(x),\mathrm{\Phi }(z))=d_G(\mathrm{\Phi }(x),w)+d_G(w,\mathrm{\Phi }(z)).\end{array}$$

Let ${\mathrm{\Phi }}^{-1}:V(G)\to X$ be the inverse of the mapping $\mathrm{\Phi }:X\to V(G)$. Then $\mathrm{\Phi }$ and ${\mathrm{\Phi }}^{-1}$ are isometries and, consequently, we have $$d(x,z)=d_G(\mathrm{\Phi }(x),\mathrm{\Phi }(z)),$$ and $$d_G(\mathrm{\Phi }(x),w)=d({\mathrm{\Phi }}^{-1}(\mathrm{\Phi }(x)),{\mathrm{\Phi }}^{-1}(w))=d(x,{\mathrm{\Phi }}^{-1}(w)),$$ and $$\begin{array}{}\text{(20)}& d_G(w,\mathrm{\Phi }(z))=d({\mathrm{\Phi }}^{-1}(w),{\mathrm{\Phi }}^{-1}(\mathrm{\Phi }(z)))=d({\mathrm{\Phi }}^{-1}(w),z).\end{array}$$

Equalities (19)–(20) imply $$\begin{array}{}\text{(21)}& d(x,z)=d(x,{\mathrm{\Phi }}^{-1}(w))+d({\mathrm{\Phi }}^{-1}(w),z),\end{array}$$ and, in addition we have $$\begin{array}{}\text{(22)}& x\ne {\mathrm{\Phi }}^{-1}(w)\ne z,\end{array}$$ by (18). Now, (15) and (16) follow from (22) and (21) with $y={\mathrm{\Phi }}^{-1}(w)$.

$(ii)\Rightarrow (i)$. Let statement $(ii)$ be valid. Then we consider a graph $G$ such that $$\begin{array}{}\text{(23)}& V(G)=X,\end{array}$$ and $$\begin{array}{}\text{(24)}& (\{p,q\}\in E(G))⟺(d(p,q)=1),\end{array}$$ for all $p,q\in X$.

We claim that $G$ is a connected graph and that the equality $$\begin{array}{}\text{(25)}& d=d_G,\end{array}$$ is satisfied, which obviously implies $(i)$.

It suffices to show that if $x$, $z\in V(G)$ are distinct, then there is a connected subgraph $G_{x,z}$ of $G$ such that $x\in V(G_{x,z})$ and $z\in V(G_{x,z})$. Let us consider arbitrary different $x,z\in V(G)$. Write $$n:=d(x,z).$$

It follows from (14) and (23) that $n$ is a positive integer. We construct the required $G_{x,z}\subseteq G$ by induction on $n$.

If $n=1$, then $x$ and $z$ adjacent in $G$ by (24). So we can define $G_{x,z}$ by $$V(G_{x,z}):=\{x,z\}\text{and}E(G_{x,z}):=\{\{x,z\}\}.$$

Suppose that we can construct $G_{x,z}$ for all $n<n_1$, where $n_1⩾2$ and that $$d(x,z)=n_1,$$ holds. Then using $(ii)$ we can find $y\in V(G)$ satisfying (15) and (16).

Now, (15) and (16) give us $$1⩽d(x,y)⩽n_1-1,$$ and $$1⩽d(y,z)⩽n_1-1.$$

Consequently, by induction hypothesis, there are connected $G_{x,y}\subseteq G$ and $G_{y,z}\subseteq G$ such that $x,y\in V(G_{x,y})$ and $y,z\in V(G_{y,z})$. Since $y\in V(G_{x,y})\cap V(G_{y,z})$, the union $G_{x,y}\cup G_{y,z}$ is a connected subgraph of $G$ by Lemma 2.4.

Write $$G_{x,z}:=G_{x,y}\cup G_{y,z},$$ then $G_{x,z}$ is connected and $x,z\in G_{x,z}$.

Thus, $G$ is a connected graph, and, consequently, the geodesic distance $d_G$ is a correctly defined metric on $V(G)$ by Proposition 2.6.

To complete the proof, we must show that (25) holds. Let $x$ and $z$ be different points of $X$. Assume first that $d(x,z)=1$. Then $x$ and $y$ are adjacent in $G$. Hence, by Lemma 2.7, we obtain $$d_G(x,z)=1.$$

Thus, the equality $$\begin{array}{}\text{(26)}& d(x,z)=d_G(x,z),\end{array}$$ holds if $d(x,z)=1$. Moreover, equality (26) holds by Definition 2.1 when $x=z$.

Suppose now that $$\begin{array}{}\text{(27)}& d(x,z)=n⩾2.\end{array}$$

Then using statement $(ii)$ we can find some points $y_1,\dots ,y_{n+1}\in X$ such that $$y_1=x_1,y_{n+1}=z,$$ and $$\begin{array}{}\text{(28)}& d(y_i,y_{i+1})=1,\end{array}$$ for every $i\in \{i,\dots ,n\}$, and $$\begin{array}{}\text{(29)}& d(x,z)=\sum _{i=1}^{n}d(y_i,y_{i+1}).\end{array}$$

It was noted above that (28) implies $$d(y_i,y_{i+1})=d_G(y_i,y_{i+1}),i=1,\dots ,n.$$

Therefore, we can rewrite (29) in the form $$d(x,z)=d_G(x,y_1)+d_G(y_1,y_2)+\dots +d_G(y_{n-1},y_n)+d_G(y_n,z).$$

The last equality and the triangle inequality give us the inequality $$\begin{array}{}\text{(30)}& d(x,z)⩾d_G(x,z).\end{array}$$

Let $P$ be a shortest path joining $x$ and $z$ in $G$, $$V(P)=\{x_0,x_1,\dots ,x_k\},k⩽1,\text{and}E(P)=\{\{x_0,x_1\},\dots ,\{x_{k-1},x_k\}\},$$ where $x_0=x$ and $x_n=z$. It follows from (27) that $$d_G(x,z)⩾2,$$ since otherwise $d_G(x,z)=d(x,z)=1$ contrary to (27). Thus, $k⩾2$ holds.

Using Definition 2.5 we obtain the equality $$d_G(x,z)=d_G(x,x_1)+d_G(x_1,x_2)+\dots +d_G(x_{k-2},x_{k-1})+d_G(x_{k-1},z).$$ Now, we can rewrite it as $$\begin{array}{}\text{(31)}& d_G(x,z)=d(x,x_1)+d(x_1,x_2)+\dots +d(x_{k-2},x_{k-1})+d(x_{k-1},z),\end{array}$$ because, for every $j\in \{0,\dots ,k-1\}$, the vertices $x_j$ and $x_{j+1}$ are adjecent that implies $d_G(x_j,x_{j+1})=d(x_j,x_{j+1})$. Equality (31) and the triangle inequality imply $$d_G(x,z)⩾d(x,z).$$

The last inequality and (30) give us $$d(x,z)=d_G(x,z).$$

Equality (25) follows.

The proof is completed. 

Proof. $(i)⟹(ii)$. Let $(i)$ hold. Then $(ii)$ directly follows from Definition 2.5.

$(ii)⟹(i)$. Suppose that inclusion (32) holds. Let us define a set $X_2$ of two-point subsets of $X$ by the rule: $\{x,y\}\in X_2$ iff $$d(x,y)⩾2,$$ and, for every $z\in X$, $$d(x,y)<d(x,z)+d(z,y),$$ whenever $$x\ne y\ne z.$$

If $X_2=\varnothing$, then $(i)$ follows from Theorem 3.1.

Let us consider the case when $X_2\ne \varnothing$. For each $\{x,y\}\in X_2$ we define a path $P_{x,y}=(v_0,\dots ,v_k)$ such that:

(1) $(i_1)$ $v_0=x$, $v_k=y$ and $v_i\notin X$ for any $i\in \{1,\dots ,k-1\}$;

(2) $(i_2)$ The equality $k=d(x,y)$ holds;

(3) $(i_3)$ If $\{x_1,y_1\}\in X_2$, $\{x_2,y_2\}\in X_2$ and $\{x_1,y_1\}\ne \{x_2,y_2\}$, then the intersection of the sets

$$\{u\in V(P_{x_1,y_1}):x_1\ne u\ne y_1\},$$ and $$\{u\in V(P_{x_2,y_2}):x_2\ne u\ne y_2\},$$ is empty.

Let us now define a graph $G$ as follows: $$\begin{array}{}\text{(33)}& V(G)=X\cup ({\cup }_{\{x,y\}\in X_2}V(P_{x,y})),\end{array}$$ and, for all $u,v\in V(G)$, $u$ and $v$ are adjacent iff either $u,v\in X$ and $d(u,v)=1$, or $\{u,v\}\in E(P_{x,y})$ for some $\{x,y\}\in X_2$.

We claim that $G$ is a connected graph.

Let us consider two arbitrary distinct $u,v\in V(G)$. It is enough to show that there is a connected subgraph $G_{u,v}$ of $G$ such that $u\in V(G_{u,v})$ and $v\in V(G_{u,v})$ if $u\in X$ and $v\in X$.

Indeed, if $u\notin X$ and $v\notin X$, then, by (33), there are $\{x_1,y_1\}\in X_2$ and $\{x_2,y_2\}\in X_2$ such that $u\in V(P_{x_1,y_1})$, and $v\in V(P_{x_2,y_2})$, and $$x_1,x_2,y_1,y_2\in X.$$

Without less of generality we may assume that $x_1\ne y_2$. Suppose that there is a connected subgraph of $G_{x_1,y_2}$ such that $$x_1,y_2\in V(G_{x_1,y_2}).$$

Then Lemma 2.4 implies that the union $P_{x_1,y_1}\cup P_{x_2,y_2}\cup G_{x_1,y_2}$ also is a connected subgraph of $G$. The cases $u\in X$, $v\notin X$ and $u\notin X$, $v\in X$ can be treated similarly, so we omit the details here.

Suppose now that $u,v\in X$ and $u\ne v$. If $d(u,v)=1$, then, by definition, $u$ and $v$ are adjacent in $G$ and, consequently, we may take $G_{u,v}$ with $$V(G_{u,v})=\{u,v\}\text{and}E(G_{u,v})=\{\{u,v\}\}.$$

If $$\begin{array}{}\text{(34)}& d(u,v)⩾2,\end{array}$$ holds and $\{u,v\}\in X_2$, then the path $P_{u,v}$ defined as in $(i_1)–(i_3)$ is a connected subgraph of $G$, and $u,v\in P_{u,v}$, so we can set $G_{u,v}:=P_{u,v}$.

Let us consider now the case when (34) is valid but $\{u,v\}\notin X_2$. Then, by definition of $X_2$, there exist some points $p_0,p_1,\dots ,p_{n+1}$ such that $$\begin{array}{}\text{(35)}& p_0=u\text{and}{p}_{n+1}=v,\end{array}$$ $$\begin{array}{}\text{(36)}& d(u,v)={\sum }_{i=0}^{n}d(p_i,p_{i+1}),\end{array}$$ and, for each $i\in \{0,1,\dots ,n+1\}$, we have $$\begin{array}{}\text{(37)}& \text{either }d(p_i,p_{i+1})=1\text{or}\{p_i,p_{i+1}\}\in X_2.\end{array}$$

The paths $P_{p_0,p_1},P_{p_1,p_2},\dots ,P_{p_n,p_{n+1}}$ are connected subgraphs of $G$. Consequently, $$G_{u,v}:={\bigcup }_{i=0}^n{P}_{p_i,p_{i+1}},$$ also is a connected subgraph of $G$ by Lemma 2.4, and $u,v\in V(G_{u,v})$ holds by definition of $G_{u,v}$.

Thus, $G$ is connected. To complete the proof we must show that the equality $$\begin{array}{}\text{(38)}& d_G(u,v)=d(u,v),\end{array}$$ holds for all $u,v\in X$.

Equality (38) holds if and only if we have $$\begin{array}{}\text{(39)}& d(u,v)⩾d_G(u,v),\end{array}$$ and $$\begin{array}{}\text{(40)}& d(u,v)⩽d_G(u,v).\end{array}$$

Let us prove (39).

If $u=v$ holds, then inequality (39) directly follows from Definition 2.1.

Let $$\begin{array}{}\text{(41)}& d(u,v)=1,\end{array}$$ hold. Then, by the definition of the graph $G$, we obtain $$\{u,v\}\in E(G).$$

Hence, by Lemma 2.7 the equality $$\begin{array}{}\text{(42)}& d_G(u,v)=1,\end{array}$$ holds. Now, (39) follows from (41) and (42).

Let us consider now the case when $u,v\in X$ and $$d(u,v)⩾2,$$ holds.

Suppose that $\{u,v\}\in X_2$, and consider the path $P_{u,v}$ satisfying conditions $(i_1)-(i_3)$ with $x=u$ and $y=v$. Then we have $$P_{u,v}\subseteq G,$$ by definition of $G$ and $$\begin{array}{}\text{(43)}& d(u,v)=|E(P_{u,v})|,\end{array}$$ by $(i_2)$. Definition 2.5 and equality (43) now imply (39).

If $\{u,v\}\notin X_2$, then there exist some points $p_0,\dots ,p_{n+1}\in X$ such that (35), (36) and (37) are valid. Using (37) we obtain $$\begin{array}{}\text{(44)}& d(u,p_1)⩾d_G(u,p),d(p_1,p_2)⩾d_G(p_1,p_2),\dots ,d(p_n,v)⩾d_G(p_n,v).\end{array}$$

Moreover, we have $$\begin{array}{}\text{(45)}& d_G(u,v)⩽d_G(u,p_1)+d_G(p_1,p_2)+\dots +d_G(p_n,v),\end{array}$$ by triangle inequality. Hence, $$d(u,v)⩾d_G(u,p_1)+d_G(p_1,p_2)+\dots +d_G(p_n,v)⩾d_G(u,v),$$ holds by (36), (44) and (45). Thus inequality (39) is valid for all $u,v\in X$.

Let us prove (40) for all $u,v\in X$. Reasoning as above we see that $d_G(u,v)=d(u,v)$ holds if $d_G(u,v)⩽1$. Thus if there are $u,v\in X$ such that (40) does not hold then there are $u^{\ast },v^{\ast }\in X$ such that $$\begin{array}{}\text{(46)}& d(u^{\ast },v^{\ast })>d_G(u^{\ast },v^{\ast }),\end{array}$$ but we have $$d(u,v)⩽d_G(u,v),$$ whenever $$d_G(u,v)<d_G(u^{\ast },v^{\ast }).$$

Let $u^{\ast }$ and $v^{\ast }$ satisfy the above conditions, and let $P_{u^{\ast },v^{\ast }}^{\ast }=\{w_0,\dots ,w_m\}$ be a path in $G$ such that $w_0=u^{\ast },\dots ,w_m=v^{\ast }$ and $$\begin{array}{}\text{(47)}& d_G(u^{\ast },v^{\ast })=|E(P_{u^{\ast },v^{\ast }}^{\ast })|.\end{array}$$

The following two cases are possible:

We have $$\begin{array}{}\text{(48)}& w_i\notin X,\end{array}$$ whenever $i\in \{1,\dots ,m-1\}$;

There is $w_{i_0}\in V(P_{u^{\ast },v^{\ast }}^{\ast })$ such that $$\begin{array}{}\text{(49)}& w_{i_0}\in X,\end{array}$$ and $i_0\in \{1,\dots ,m-1\}$.

In the first case it follows from (33) and (48) that there is a path $P_{x,y}$ satisfying conditions $(i_1)-(i_3)$ such that $$w_1\in V(P_{x,y}).$$

Conditions $(i_1)$ and $(i_3)$ imply the equality $$V(P_{x,y})=V(P_{u^{\ast },v^{\ast }}^{\ast }).$$

Now, using $(i_2)$ we see that (49) implies $$\begin{array}{}\text{(50)}& |E(P_{x,y})|=d(x,y)=d(u^{\ast },v^{\ast })=|E(P_{u^{\ast },v^{\ast }}^{\ast })|.\end{array}$$

Equalities (50) and (47) give us $$d_G(u^{\ast },v^{\ast })=d(u^{\ast },v^{\ast }),$$ contrary to (46).

Let us consider the case when there is $w_{i_0}\in V(P_{u^{\ast },v^{\ast }}^{\ast })$ such that (49) holds and $$\begin{array}{}\text{(51)}& i_0\in \{1,\dots ,m-1\}.\end{array}$$

By Lemma 2.8 we have $$\begin{array}{}\text{(52)}& d_G(u^{\ast },v^{\ast })=d_G(u^{\ast },w_{i_0})+d_G(w_{i_0},v^{\ast }).\end{array}$$

Moreover, (51) implies that $$\begin{array}{}\text{(53)}& u^{\ast }\ne w_{i_0}\ne v^{\ast }.\end{array}$$

Now, it follows from (52) and (53) that $$d_G(u^{\ast },w_{i_0})<d_G(u^{\ast },v^{\ast }),$$ and $$d_G(w_{i_0},v^{\ast })<d_G(u^{\ast },v^{\ast }).$$

Hence, by definition of the points $u^{\ast },v^{\ast }$, the equalities $$\begin{array}{}\text{(54)}& d_G(u^{\ast },w_{i_0})=d(u^{\ast },w_{i_0}),\end{array}$$ $$\begin{array}{}\text{(55)}& d_G(w_{i_0},v^{\ast })=d(w_{i_0},v^{\ast }),\end{array}$$ hold. Now, using (52), the triangle inequality in $(X,d)$, and equalities (54)–(55) we obtain $$d_G(u^{\ast },v^{\ast })=d(u^{\ast },w_{i_0})+d(w_{i_0},v^{\ast })⩾d(u^{\ast },v^{\ast }),$$ which contradicts (46). Thus, (40) holds for all $u,v\in X$.

The proof is completed. 

Proof. Let ${\mathbb{R}}^{+}\ni t\mapsto \lceil t\rceil \in {\mathbb{N}}_0$ be the sailing function, $$\begin{array}{}\text{(57)}& \lceil t\rceil =min\{n\in {\mathbb{N}}_0:n⩾t\},\end{array}$$ for each $t\in {\mathbb{R}}^{+}$. It is known that, for each metric space $(X,d)$, the function $$\begin{array}{}\text{(58)}& X\times X\ni (x,y)\mapsto \lceil d(x,y)\rceil \in {\mathbb{R}}^{+},\end{array}$$ remains a metric on $X$. (See, for example, [3, Corollary 1, p. 6]). Write $\lceil d\rceil$ for the metric on $X$ defined by (58). Since $\lceil t\rceil$ is integer for every $t\in {\mathbb{R}}^{+}$, Corollary 3.4 implies that the metric space $(X,\lceil d\rceil )$ is isometrically embedded in $(V(G),d_G)$ for some connected graph $G$. Let $\mathrm{\Phi }:X\to V(G)$ be an isometric embedding of $(X,\lceil d\rceil )$ in $(V(G),d_G)$. Then $$\lceil d(x,y)\rceil =\lceil d\rceil (x,y)=d_G(\mathrm{\Phi }(x),\mathrm{\Phi }(y)),$$ holds for all $x,y\in X$. Moreover, we have $$\begin{array}{}\text{(59)}& t⩽\lceil t\rceil <t+1,\end{array}$$ for every $t\in {\mathbb{R}}^{+}$ by (57). Now, (56) follows from (58)–(59).