Let \(G\) be a connected graph and let \(d_G\) be the geodesic distance on \(V(G)\). The metric spaces \((V(G), d_{G})\) were characterized up to isometry for all finite connected \(G\) by David C. Kay and Gary Chartrand in 1965. The main result of this paper expands this characterization on infinite connected graphs. We also prove that every metric space with integer distances between its points admits an isometric embedding in \((V(G), d_G)\) for suitable \(G\).
Let \(u,v \in V(G)\) be vertices of a connected graph \(G\). Then the geodesic distance \(d_G (u,v)\) is the minimum size of paths joining \(u\) and \(v\) in \(G\). There are some important interconnections between metric properties of the space \((V(G), d_G )\) and combinatorial properties of \(G\), [7,14]. It should be noted here that almost all of these interconnections were found for finite graphs. In particular, the following theorem was proved by David C. Kay and Gary Chartrand in [8].
Theorem 1.1. Let \((M,d)\) be a finite metric space. Then \((M,d)\) is isometric to the space \((V(G), d_G)\) for some finite connected \(G\) if and only if the distance between every two points of \(M\) is an integer and, for arbitrary \(x,z \in M\) with \(d(x,z) \geqslant 2\), there is \(y \in M\) such that \(y\) lies between \(x\) and \(z\).
The initial goal of the paper is to extend the above theorem to connected graphs of arbitrary infinite order.
The paper is organized as follows. Section 2 contains some definitions and facts from the theory of metric spaces and graph theory.
The main results are given in Section 3. In Theorem 3.1, an extension of Theorem 1.1 to arbitrary infinite graphs is proved.
In Theorem 3.3, we prove that each metric space with integer distances between points admits an isometric embedding into \((V(G), d_G)\) for some connected \(G\). A weak version of Theorem 3.3 is given in Corollary 3.5 for metric spaces with arbitrary distances between points.
A graph-theoretical reformulation of Menger’s results on isometric embeddings in the real line is given in Conjecture 4.2 of Section 4. An extremal property of pseudo-linear quadruples is presented as a property of induced cycles in Conjecture 4.4.
Let us recall some concepts from the theory of metric spaces and graph theory.
Definition 2.1. Let \(X\) be a nonempty set. A metric on \(X\) is a function \(d : X \times X \to \mathbb{R}^+,\) \(\mathbb{R}^+ = [0, \infty)\), such that for all \(x, y, z \in X\):
(i) \(d(x, y) = d(y, x)\), symmetry;
(ii) \((d(x, y) = 0) \Leftrightarrow (x = y)\), non-negativity;
(iii) \(d(x, y) \leqslant d(x, z) + d(z, y)\), triangle inequality.
The main isomorphisms of metric spaces are the so-called isometries of such spaces.
Definition 2.2. The metric spaces \((X, d)\) and \((Y, \rho)\) are isometric if there is a bijective mapping \(\Phi : X \to Y\) such that \[\label{def2.1_eq1} d(x, y) = \rho(\Phi(x), \Phi(y)), \tag{1}\] for all \(x, y \in X\). In this case, we say that \(\Phi\) is an isometry of \((X, d)\) and \((Y, \rho)\).
Let \((X, d)\) and \((Y, \rho)\) be metric spaces. Recall that \(\Phi : X \to Y\) is an isometric embedding of \((X, d)\) in \((Y, \rho)\) if (1) holds for all \(x, y \in X\). We say that \((X, d)\) is isometrically embedded in \((Y, \rho)\) if there exists an isometric embedding \(X \to Y\).
We will also use the concept of “metric betweenness”. In the theory of metric spaces, the notion of “metric betweenness”, first appeared in Menger’s paper [11].
Definition 2.3. Let \((X,d)\) be a metric space and let \(x\), \(y, z\) be points of \((X,d)\). One says that \(y\) lies between \(x\) and \(z\) if \(x \neq y \neq z\) and \[%\label{def2.4_eq1} d (x, z) = d (x, y) + d (y, z).\]
The relation “betweenness” is fundamental for the theory of geodesics on metric spaces (see, e.g., [13]). Characteristic properties of the ternary relations that are “metric betweenness” relations for (real-valued) metrics were determined by Wald in [16]. Later, the problem of “metrization” of betweenness relations (not necessarily by real-valued metrics) was considered in [10,12] and [15]. An infinitesimal version of the metric betweenness was studied in [1] and [6]. Paper [2] contains an explicit construction of a minimal metric space \((Y, \rho)\) such that a metric space \((X,d)\) is isometrically embedded in \((Y, \rho)\) if, among any three distinct points of \(X\), there is one that lies between the others. An elementary proof of some Menger’s results was given in [5].
A graph is a pair \((V, E)\) consisting of a nonempty set \(V\) and a (possibly empty) set \(E\) whose elements are unordered pairs of different points from \(V\). For a graph \(G = (V, E)\), the sets \(V = V(G)\) and \(E = E(G)\) are called the set of vertices and the set of edges, respectively. We say that \(G\) is nonempty if \(E(G) \neq \varnothing\). If \(\{x, y\} \in E(G)\), then the vertices \(x\) and \(y\) are adjacent. Recall that a path is a nonempty graph \(P\) whose vertices can be numbered so that \[%\label{s2_eq0} V(P) = \{ x_0, x_1, \ldots, x_k\}, \ E(P ) = \{ \{ x_0, x_1\}, \ldots, \{x_{k-1}, x_k\} \},\] where \(k \geqslant 1\). In this case, we say that \(P\) is a path joining \(x_0\) and \(x_k\) and write \[P= (x_0, x_1, \ldots, x_k).\]
A graph \(G\) is finite if \(V (G)\) is a finite set, \(|V (G)| < \infty\). The cardinal number \(|V(G)|\) is called order of \(G\). In this paper, we consider graphs with arbitrary finite or infinite order.
A finite graph of order \(n \geqslant 3\) is called the cycle \(C_n\) if there exists an enumeration \(v_1, v_2, \ldots, v_n\) of its vertices such that \[( \{ v_i, v_j \} \in E(C_n)) \Leftrightarrow (|i – j| = 1 \quad \textrm{or} \quad |i – j| = n – 1).\]
In this case, we write \(C_n = (v_1, \ldots, v_n, v_1)\).
A graph \(H\) is a subgraph of a graph \(G\) if \[V (H) \subseteq V (G) \quad \textrm{and} \quad E(H) \subseteq E(G).\]
We write \(H \subseteq G\) if \(H\) is a subgraph of \(G\).
If \(H_1\) and \(H_2\) are subgraphs of \(G\), then the union \(H_1 \cup H_2\) is a subgraph of \(G\) such that \[V(H_1 \cup H_2) = V(H_1) \cup V(H_2) \quad \textrm{and} \quad E(H_1 \cup H_2) = E(H_1) \cup E(H_2).\]
A graph \(G\) is connected if for every two distinct \(u, v \in V (G)\) there is a path \(P \subseteq G\) joining \(u\) and \(v\).
The following lemma is well-known.
Lemma 2.4. Let \(G_1\) and \(G_2\) be connected subgraphs of a graph \(G\). If \[%\label{lem2.4_eq1} V(G_1) \cap V(G_2) \neq \varnothing,\] holds, then the union \(G_1 \cup G_2\) also is a connected subgraph of \(G\).
Let us now recall the concept of geodesic distance on graphs.
Definition 2.5. Let \(G\) be a connected graph. For each two vertices \(u,v \in V(G)\) we define the geodesic distance \(d_G(u,v)\) as \[\label{def2.3_eq1} d_G (u,v) = \left\{ \begin{array}{ll} 0, & \quad \hbox{if} \quad u=v, \\ |E(P)|, & \quad \hbox{otherwise,} \end{array} \right. \tag{2}\] where \(P\) is a shortest path joining \(u\) and \(v\) in \(G\).
The following proposition is well-known but is usually formulated without any proof. See, for example, [14] or Remark 1.16 in [9].
Proposition 2.6. Let \(G\) be a connected graph. Then the geodesic distance \(d_G\) is a metric on \(V(G)\).
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 \[\label{pr2.4_preq1} d_G(u,v) \leqslant d_G (u,w) + d_G(w,v), \tag{3}\] 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\); \[\label{pr2.4_preq2} d_G(u,w) = | E(P_{u,w})|, \tag{4}\] and \[\label{pr2.4_preq3} d_G(w,v) = | E(P_{w,v})|. \tag{5}\]
Write \[\label{pr2.4_preq4} G_1 : = P_{u,w} \cup P_{w,v}. \tag{6}\]
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 \[\label{pr2.4_preq5} d_G(u,v) \leqslant d_{G_1} (u,w), \tag{7}\] holds.
Inequality (7) implies that (3) holds if \[%\label{pr2.4_preq6} d_{G_1}(u,v) \leqslant d_G (u,w) + d_G(w,v).\]
Let \(P^{1}_{u,v}\) be a path joining \(u\) and \(v\) in \(G_1\) such that \[%\label{pr2.4_preq7} d_G(u,v) =|E(P^1_{u,v})|.\]
It follows directly from the definition of paths that \[\label{pr2.4_preq8} |E(P_{u,w})| = |V (P_{u,w})| -1, \tag{8}\] \[\label{pr2.4_preq9} |E(P_{w,v})| = |V (P_{w,v})|-1, \tag{9}\] and \[\label{pr2.4_preq10} |E(P^1_{u,v})| = |V (P^1_{u,v})|-1. \tag{10}\]
Now, using (4)–(5), (6), and (8)–(9) we obtain \[\label{pr2.4_preq11} \begin{aligned} 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{aligned} \tag{11}\]
Since \(w\) belongs to \(V(P_{u,w}) \cap V(P_{w,v})\), (11) implies \[\label{pr2.4_preq12} d_G(u,w) + d_G(w,v) \geqslant |V (G_1)|-1. \tag{12}\]
Similarly, it follows from \(P^1_{u,v} \subseteq G_1\) and (10) that \[\label{pr2.4_preq13} d_{G_1} (u,v) = |V(P^1_{u,v})| -1 \leqslant |V(G_1)|-1. \tag{13}\]
Inequality (3) follows from (7), (12) and (13).
The proof is completed. ◻
The following simple lemmas will be used in the next section of the paper.
Lemma 2.7. Let \(G\) be a connected graph and let \(u,v \in V(G)\). Then the vertices \(u\) and \(v\) are adjacent if and only if the equality \[%\label{lem2.6_eq1} d_G (u,v) = 1,\] holds.
Lemma 2.8. Let \(G\) be a connected graph, let \(x\) and \(z\) be different vertices of \(G\), and let \(P\) be a shortest path joining \(x\) and \(z\). Then every \(y \in V(P)\) lies between \(x\) and \(z\), whenever \(x \neq y \neq z\).
The following theorem shows that the Kay–Chartrand characterization of spaces \((V(G), d_G)\) is valid for connected graphs \(G\) of arbitrary order.
In what follows, we denote by \(\mathbb{N}_0\) the set of all nonnegative integers, \(\mathbb{N}_0 = \{0, 1, 2, \ldots\}\).
Theorem 3.1. Let \((X, d)\) be a metric space. Then the following statements are equivalent.
(i) There exists a connected graph \(G\) such that the metric spaces \((X, d)\) and \((V(G), d_G)\) are isometric.
(ii) The inclusion \[\label{th3.6_eq2} \{d(p,q)\colon p,q \in X\} \subseteq\mathbb{N}_0, \tag{14}\] holds and, for any two points \(x,z \in X\) satisfying the inequality \(d(x,z) \geqslant 2\), there is \(y \in X\) that lies between \(x\) and \(z\).
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) \geqslant 2\). We need to show that there exists a point \(y \in X\) such that \[\label{th3.6_eq4} x \neq y \neq z, \tag{15}\] and \[\label{th3.6_eq5} d(x,z) = d(x,y) + d(y,z). \tag{16}\]
Let \(\Phi\colon X \to V(G)\) be an isometry between the metric spaces \((X,d)\) and \((V(G), d_G)\). Then the inequality \[\label{th3.3_preq1} d_G (\Phi(x), \Phi(z)) \geqslant 2, \tag{17}\] holds by Definition 2.2. Let \(P\) be a path in \(G\) joining \(\Phi(x)\) and \(\Phi(z)\) such that \[d_G (\Phi(x), \Phi(z)) = |E(P)|.\]
Inequality (17) implies \(|E(P)| \geqslant 2\). Consequently, there is \(w \in V(P)\) such that \[\label{th3.3_preq2} \Phi(x) \neq w \neq \Phi(z). \tag{18}\]
Now, using Lemma 2.8 we obtain \[\label{th3.3_preq3} d_G (\Phi(x), \Phi(z)) = d_G (\Phi(x), w) + d_G (w, \Phi(z)). \tag{19}\]
Let \(\Phi^{-1}: V(G) \to X\) be the inverse of the mapping \(\Phi: X \to V(G)\). Then \(\Phi\) and \(\Phi^{-1}\) are isometries and, consequently, we have \[%\label{th3.3_preq4} d(x, z) = d_G (\Phi(x), \Phi(z)),\] and \[%\label{th3.3_preq5} d_G (\Phi(x), w) = d(\Phi^{-1} \left( \Phi(x)\right), \Phi^{-1}(w)) = d(x, \Phi^{-1} (w)),\] and \[\label{th3.3_preq6} d_G (w, \Phi(z)) = d(\Phi^{-1} (w), \Phi^{-1}(\Phi(z))) = d(\Phi^{-1} (w), z). \tag{20}\]
Equalities (19)–(20) imply \[\label{th3.3_preq7} d(x, z) = d(x, \Phi^{-1}(w)) + d(\Phi^{-1} (w), z), \tag{21}\] and, in addition we have \[\label{th3.3_preq8} x \neq \Phi^{-1}(w) \neq z, \tag{22}\] by (18). Now, (15) and (16) follow from (22) and (21) with \(y = \Phi^{-1} (w)\).
\((ii) \Rightarrow (i)\). Let statement \((ii)\) be valid. Then we consider a graph \(G\) such that \[\label{th3.6_preq0} V(G) = X, \tag{23}\] and \[\label{th3.6_preq1} \left(\{p, q\} \in E(G) \right) \Longleftrightarrow (d(p, q)=1), \tag{24}\] for all \(p, q \in X\).
We claim that \(G\) is a connected graph and that the equality \[\label{th3.6_preq2} d=d_G, \tag{25}\] 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 \[%\label{th3.6_preq3} 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\} \quad \textrm{and} \quad E(G_{x,z}):= \{\{x,z\}\}.\]
Suppose that we can construct \(G_{x, z}\) for all \(n<n_1\), where \(n_1 \geqslant 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 \leqslant d(x,y) \leqslant n_1-1,\] and \[1 \leqslant d(y,z) \leqslant 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 \[\label{th3.6_preq6} d(x,z) = d_G(x,z), \tag{26}\] holds if \(d(x,z) =1\). Moreover, equality (26) holds by Definition 2.1 when \(x=z\).
Suppose now that \[\label{th3.6_preq7} d(x,z) = n \geqslant 2. \tag{27}\]
Then using statement \((ii)\) we can find some points \(y_1, \ldots, y_{n+1} \in X\) such that \[%\label{th3.6_preq8} y_1 = x_1, \quad y_{n+1} = z,\] and \[\label{th3.6_preq9} d(y_i, y_{i+1}) = 1, \tag{28}\] for every \(i \in \{ i, \ldots, n\}\), and \[\label{th3.6_preq10} d(x,z) = \sum_{i=1}^n d(y_i, y_{i+1}). \tag{29}\]
It was noted above that (28) implies \[d(y_i, y_{i+1}) =d_G (y_i, y_{i+1}), \quad i= 1, \ldots, n.\]
Therefore, we can rewrite (29) in the form \[d(x,z) = d_G(x,y_1) + d_G(y_1, y_2) + \ldots + d_G(y_{n-1}, y_n) + d_G(y_n,z).\]
The last equality and the triangle inequality give us the inequality \[\label{th3.6_preq11} d(x,z) \geqslant d_G(x,z). \tag{30}\]
Let \(P\) be a shortest path joining \(x\) and \(z\) in \(G\), \[%\label{th3.6_preq12} V(P) = \{ x_0, x_1, \ldots, x_k\}, \ k \leqslant 1, \ \textrm{and} \ E(P ) = \{ \{ x_0, x_1\}, \ldots, \{x_{k-1}, x_k\} \},\] where \(x_0=x\) and \(x_n =z\). It follows from (27) that \[d_G (x,z) \geqslant 2,\] since otherwise \(d_G (x,z) = d(x,z) =1\) contrary to (27). Thus, \(k \geqslant 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) + \ldots + d_G (x_{k-2}, x_{k-1}) + d_G (x_{k-1}, z).\] Now, we can rewrite it as \[\label{th3.6_preq13} d_G(x,z) = d(x,x_1) + d(x_1, x_2) + \ldots + d(x_{k-2}, x_{k-1}) + d (x_{k-1}, z), \tag{31}\] because, for every \(j \in \{ 0, \ldots, 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) \geqslant d(x,z).\]
The last inequality and (30) give us \[d(x,z) = d_G (x,z).\]
Equality (25) follows.
The proof is completed. ◻
Analyzing the above proof, we obtain the following clarification of Theorem 3.1.
Theorem 3.2. Let \((X,d)\) be a metric space and let \[\{d(p,q)\colon p,q \in X\} \subseteq \mathbb{N}_0.\]
If, for any \(x,z \in X\) satisfying \(d(x,z) \geqslant 2\), there is \(y \in X\) such that \(y\) lies between \(x\) and \(z\), then the graph \(G\) defined by \(V(G) =X\) and \[\left( \{x,y\} \in E(G) \right) \Longleftrightarrow (d(x,y) = 1),\] is connected and the geodesic distance \(d_G\) satisfies the equality \(d = d_G.\)
The following theorem shows that metric spaces with integer distances between points are subspaces of the spaces \((V(G), d_G)\).
Theorem 3.3. Let \((X,d)\) be a metric space. Then the following statements are equivalent.
(i) There is a connected graph \(G\) such that \((X,d)\) is isometric to a subspace of \((V(G), d_G)\).
(ii) The inclusion \[\label{th3.5_eq1} \{d(p,q)\colon p,q \in X\} \subseteq\mathbb{N}_0, \tag{32}\] holds.
Proof. \((i) \Longrightarrow (ii)\). Let \((i)\) hold. Then \((ii)\) directly follows from Definition 2.5.
\((ii) \Longrightarrow (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 \[%\label{th3.5_preq1} d(x,y) \geqslant 2,\] and, for every \(z \in X\), \[%\label{th3.5_preq2} d(x,y) < d(x,z) + d(z,y),\] whenever \[%\label{th3.5_preq3} x \neq y \neq z.\]
If \(X_2= \varnothing\), then \((i)\) follows from Theorem 3.1.
Let us consider the case when \(X_2 \neq \varnothing\). For each \(\{ x,y\} \in X_2\) we define a path \(P_{x,y} = (v_0, \ldots, v_k)\) such that:
(1) \((i_1)\) \(v_0=x\), \(v_k =y\) and \(v_i \notin X\) for any \(i \in \{ 1, \ldots, 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\} \neq \{x_2, y_2\}\), then the intersection of the sets
\[\{u \in V(P_{x_1, y_1})\colon x_1 \neq u \neq y_1 \},\] and \[\{u \in V(P_{x_2, y_2})\colon x_2 \neq u \neq y_2 \},\] is empty.
Let us now define a graph \(G\) as follows: \[\label{th3.5_preq4} V(G) = X \cup \left( \cup_{\{x,y\} \in X_2} V (P_{x,y}) \right), \tag{33}\] 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 \neq 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 \neq 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\} \quad \textrm{and} \quad E(G_{u,v}) = \{ \{u,v\}\}.\]
If \[\label{th3.5_preq5} d(u,v) \geqslant 2, \tag{34}\] 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, \ldots, p_{n+1}\) such that \[\label{th3.5_preq6_0} p_0=u \quad \textrm{and} \quad p_{n+1} =v, \tag{35}\] \[\label{th3.5_preq6} d(u,v) = {\sum}^{n}_{i=0} d(p_i, p_{i+1}), \tag{36}\] and, for each \(i \in \{0, 1, \ldots, n+1\}\), we have \[\label{th3.5_preq7} \textrm{either } \quad d(p_i, p_{i+1}) =1 \quad \textrm{or} \quad \{p_i, p_{i+1}\} \in X_2. \tag{37}\]
The paths \(P_{p_0,p_1}, P_{p_1, p_2}, \ldots, 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 \[\label{th3.5_preq8} d_G (u,v) = d(u,v), \tag{38}\] holds for all \(u,v \in X\).
Equality (38) holds if and only if we have \[\label{th3.5_preq11} d(u,v) \geqslant d_G (u,v), \tag{39}\] and \[\label{th3.5_preq12} d(u,v) \leqslant d_G (u,v). \tag{40}\]
Let us prove (39).
If \(u=v\) holds, then inequality (39) directly follows from Definition 2.1.
Let \[\label{th3.5_preq9} d(u,v) = 1, \tag{41}\] hold. Then, by the definition of the graph \(G\), we obtain \[\{u,v\} \in E(G).\]
Hence, by Lemma 2.7 the equality \[\label{th3.5_preq10} d_G (u,v) =1, \tag{42}\] holds. Now, (39) follows from (41) and (42).
Let us consider now the case when \(u,v \in X\) and \[d(u,v) \geqslant 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 \[%\label{th3.5_preq13} P_{u,v} \subseteq G,\] by definition of \(G\) and \[\label{th3.5_preq14} d(u,v) = |E(P_{u,v})|, \tag{43}\] 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, \ldots, p_{n+1} \in X\) such that (35), (36) and (37) are valid. Using (37) we obtain \[\label{th3.5_preq15} d(u,p_1) \geqslant d_G (u,p), \ d(p_1, p_2) \geqslant d_G (p_1, p_2), \ \ldots, \ d(p_n, v) \geqslant d_G (p_n, v). \tag{44}\]
Moreover, we have \[\label{th3.5_preq16} d_G(u,v) \leqslant d_G (u,p_1) + d_G (p_1, p_2) + \ldots + d_G (p_n, v), \tag{45}\] by triangle inequality. Hence, \[d(u,v) \geqslant d_G (u,p_1) + d_G (p_1, p_2) + \ldots + d_G (p_n, v) \geqslant 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) \leqslant 1\). Thus if there are \(u,v \in X\) such that (40) does not hold then there are \(u^*, v^* \in X\) such that \[\label{th3.5_preq17} d(u^*,v^*) > d_G (u^*,v^*), \tag{46}\] but we have \[%\label{th3.5_preq18} d(u,v) \leqslant d_G (u,v),\] whenever \[%\label{th3.5_preq19} d_G(u,v) < d_G (u^*,v^*).\]
Let \(u^*\) and \(v^*\) satisfy the above conditions, and let \(P^*_{u^*,v^*} = \{w_0, \ldots, w_m\}\) be a path in \(G\) such that \(w_0 = u^*, \ldots, w_m=v^*\) and \[\label{th3.5_preq20} d_G(u^*,v^*) = |E(P^*_{u^*,v^*})|. \tag{47}\]
The following two cases are possible:
We have \[\label{th3.5_preq21} w_i \notin X, \tag{48}\] whenever \(i \in \{1, \ldots, m-1\}\);
There is \(w_{i_0} \in V(P^*_{u^*, v^*})\) such that \[\label{th3.5_preq22} w_{i_0} \in X, \tag{49}\] and \(i_0 \in \{1, \ldots, 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 \[%\label{th3.5_preq24} V(P_{x,y}) = V(P^*_{u^*,v^*}).\]
Now, using \((i_2)\) we see that (49) implies \[\label{th3.5_preq25} |E(P_{x,y})| = d(x,y) = d(u^*, v^*) = |E(P^*_{u^*, v^*})|. \tag{50}\]
Equalities (50) and (47) give us \[d_G(u^*,v^*) =d (u^*, v^*),\] contrary to (46).
Let us consider the case when there is \(w_{i_0} \in V(P^*_{u^*, v^*})\) such that (49) holds and \[\label{th3.5_preq26} i_0 \in \{ 1, \ldots, m-1\}. \tag{51}\]
By Lemma 2.8 we have \[\label{th3.5_preq27} d_G (u^*, v^*) = d_G (u^*, w_{i_0}) + d_G (w_{i_0}, v^*). \tag{52}\]
Moreover, (51) implies that \[\label{th3.5_preq28} u^* \neq w_{i_0} \neq v^*. \tag{53}\]
Now, it follows from (52) and (53) that \[d_G (u^*, w_{i_0}) < d_G (u^*, v^*),\] and \[d_G (w_{i_0}, v^*) < d_G (u^*, v^*).\]
Hence, by definition of the points \(u^*, v^*\), the equalities \[\label{th3.5_preq29} d_G (u^*, w_{i_0}) = d (u^*, w_{i_0}), \tag{54}\] \[\label{th3.5_preq30} d_G (w_{i_0}, v^*) = d (w_{i_0}, v^*), \tag{55}\] hold. Now, using (52), the triangle inequality in \((X,d)\), and equalities (54)–(55) we obtain \[d_G (u^*, v^*) = d (u^*, w_{i_0}) + d(w_{i_0}, v^*) \geqslant d (u^*, v^*),\] which contradicts (46). Thus, (40) holds for all \(u,v \in X\).
The proof is completed. ◻
Corollary 3.4. Let \((X,d)\) be a metric space. Then the following statements are equivalent.
(i) There is a connected graph \(G\) such that \((X,d)\) is isometrically embedded in \((V(G), d_G)\).
(ii) The distance between any two points of \(X\) is an integer number.
Corollary 3.5. For every metric space \((X,d)\) there exists a connected graph \(G\) and an injective mapping \(\Phi: X \to V(G)\) such that \[\label{cor3.7_eq1} d(x,y) \leqslant d_G (\Phi(x), \Phi(y)) < d(x,y) +1, \tag{56}\] for all \(x,y \in X\).
Proof. Let \(\mathbb{R}^+ \ni t \mapsto \lceil t \rceil \in \mathbb{N}_0\) be the sailing function, \[\label{cor3.7_preq1} \lceil t \rceil = \min \{n \in \mathbb{N}_0 : n \geqslant t\}, \tag{57}\] for each \(t \in \mathbb{R}^+\). It is known that, for each metric space \((X,d)\), the function \[\label{cor3.7_preq2} X \times X \ni (x,y) \mapsto \lceil d(x,y) \rceil \in \mathbb{R}^+, \tag{58}\] 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 \(\Phi: X \to V(G)\) be an isometric embedding of \((X, \lceil d \rceil )\) in \((V(G), d_G)\). Then \[%\label{cor3.7_preq3} \lceil d (x,y) \rceil = \lceil d \rceil (x,y) = d_G (\Phi(x), \Phi(y)),\] holds for all \(x,y \in X\). Moreover, we have \[\label{cor3.7_preq4} t \leqslant \lceil t \rceil < t+1, \tag{59}\] for every \(t \in \mathbb{R}^+\) by (57). Now, (56) follows from (58)–(59). ◻
Let us denote by \(\mathfrak{MB}\) the class of all metric spaces \((X,d)\) such that the equality \[d(x,z) = d(x,y) + d(y,z),\] holds whenever \(d(x,z) \geqslant \max \{ d(x,y), d(y,z)\}\) .
The following is the particular case of the classical Menger’s result on the isometric embeddings into Euclidean spaces.
Theorem 4.1. [11] Let \((Y, \rho) \in \mathfrak{M B}\) be a metric space with \(|Y| \geqslant 5\). Then \((Y, \rho)\) is isometric to some subspace of \(\mathbb{R}\).
It was also proved by K. Menger in [11], that a four-point metric space \((X,d) \in \mathfrak{M B}\) cannot be isometrically embedded in \(\mathbb{R}\) if and only if the points of \(X\) can be labelled \(x_1, x_2, x_3, x_4\) such that \[d(x_1, x_2) = d(x_3, x_4) = s, \quad d(x_2, x_3) = d(x_1, x_4) = t,\] \[\label{s4_eq1} d(x_1, x_3) = d(x_2, x_4) = s + t, \tag{60}\] where \(s\) and \(t\) are some positive constants.
The ordered four-point metric spaces \(\{x_1, x_2, x_3, x_4\}\) satisfying (60) are sometimes referred as pseudo-linear quadruples. If (60) holds with \(s=t\), then we say that the corresponding \(\{x_1, x_2, x_3, x_4\}\) is an equilateral pseudo-linear quadruple.
Recall that an infinite graph \(R\) of the form \[\begin{aligned} V (R) &= \{v_1, v_2, \ldots , v_n, v_{n+1}, \ldots \},\\ E(R) &= \{ \{v_1, v_2\}, \ldots, \{ v_n, v_{n+1} \}, \ldots \}, \end{aligned}\] is called a ray.
Moreover, a graph \(DR\) is called a double ray if \[V(DR) = \{\ldots, v_{-2}, v_{-1}, v_0, v_1, v_2, \ldots\},\] and \[E(DR)= \{\ldots, \{v_{-2}, v_{-1}\}, \{v_{-1}, v_0\}, \{v_0, v_1\}, \{v_1, v_2\}, \ldots\}.\]
The following conjecture presents a reformulation of the above-mentioned Menger’s result in the language of graph theory. This conjecture should be proved, at least partially.
Conjecture 4.2. Let \(G\) be a nonempty connected graph. Then \((V(G), d_G) \in \mathfrak{M B}\) if and only if one of the following statements holds.
(i) \(G\) is isomorphic to a path.
(ii) \(G\) is isomorphic to the cycle \(C_{4}\).
(iii) \(G\) is isomorphic to a ray \(R\).
(iv) \(G\) is isomorphic to a double ray \(DR\).
The following theorem is a special case of Theorem 1 of paper [4].
Theorem 4.3. Let \((X, d)\) be a metric space, and \(\{x_1, x_2, x_3, x_4\}\) be an ordered four-point subspace of \((X,d)\). Write \[p =d(x_1, x_2) + d(x_2, x_3) + d(x_3, x_4) + d(x_4, x_1).\]
Then we have \[\label{th4.3_eq1} d(x_1, x_3) d(x_2, x_4) – d(x_1, x_2) d(x_3, x_4) – d(x_4, x_1) d(x_2, x_3) \leqslant \frac{p^2}{8}. \tag{61}\]
The equality in (61) is attained if and only if \(\{ x_1, x_2, x_3, x_4 \}\) is an equilateral pseudo-linear quadruple.
Recall that a subgraph \(H\) of a graph \(G\) is called an induced subgraph of \(G\) if any two vertices \(u,v\) of \(H\) are adjacent in \(H\) whenever these vertices are adjacent in \(G\), \[\left( \{u,v\} \in E(H)\right) \Longleftrightarrow \left( \{u,v\} \in E(G) \right).\]
The next conjecture is a reformulation of the second path of Theorem 4.3 for the case of geodesic distances on graphs.
Conjecture 4.4. Let \(G\) be a nonempty connected graph and let \(X\) be a four-point subspace of \((V(G), d_G)\). Then the following statements are equivalent.
(i) If \(H\) is the induced subgraph of \(G\) and \(V(H) = X\), then \(H\) is a cycle.
(ii) The points of \(X\) can be ordered such that the ordered four-point subspace \(X = \{x_1, x_2, x_3, x_4\}\) of \((V(G), d_G)\) is an equilateral pseudo-linear quadruple.
The author was supported by grant 359772 of the Academy of Finland.
The author expresses the gratitude to anonymous referees, whose non-trivial remarks strongly helped in the preparing of the final version of this paper.
The author declares that there is no potential conflict of interest.