A discrete Hopf-Rinow-theorem
Matthias Keller Florentin Münch

Hopf-Rinow]A  discrete Hopf-Rinow-theorem



M. Keller]Matthias Keller
F. Münch]Florentin  Münch
Matthias Keller, Florentin Münch, Universität Potsdam, Institut für Mathematik, 14476  Potsdam, Germany
matthias.keller@uni-potsdam.de
chmuench@uni-potsdam.de











[
    [
    December 30, 2023
=====================









We prove a version of the Hopf-Rinow-theorem with respect to path metrics on discrete spaces. The novel aspect is that we do not a priori assume local finiteness but isolate a local finiteness type condition, called essential local finiteness,  that is indeed necessary. As a side product  we identify the maximal weight, called the geodesic weight, which generates the path metric in the situation when the space is complete with respect to any of the equivalent notions of completeness proven in the Hopf-Rinow theorem. As an application, we characterize the graphs for which  the resistance metric is a path metric induced by the graph structure.








§ INTRODUCTION

In 1931  Hopf and Rinow, <cit.>, have proven a most fundamental theorems in differential geometry about the equivalence of metric and geodesic completeness, as well as compactness of distance balls on Riemannian manifolds. For a modern reference we refer to <cit.>. 



Recently, the investigation of metrics on graphs have gained strong momentum. Specifically, path metrics play an important role in the study of operator theory <cit.>, spectral geometry <cit.> and the heat equation <cit.>. While the interest was first in locally finite graphs only, nowadays general weighted graphs gain more importance <cit.> as a crucial example class of non-local Dirichlet forms and their associated jump processes. Thus, geometric results which establish the analogy to the continuum setting of Riemannian manifolds are essential.


As for a Hopf-Rinow theorem, first discrete versions  have been proven in  <cit.> and <cit.>. The argument given in <cit.> is based on length spaces in the sense of
Burago-Burago-Ivanov <cit.> and, while not mentioned explicitly, the length spaces in question are metric graphs
associated to discrete graphs. On the other hand, the proof given in <cit.> is purely combinatorial.

In both of these,  the assumption of local finiteness of is central. Specifically in <cit.>, examples are given which show that this assumption can not simply be removed.

The purpose of this article is to investigate the question to which extent this assumption is also necessary. The answer is that we only need a property to which we refer to as essential local finiteness.  Essential local finiteness means that for every vertex the number of vertices which are “close” is  finite which will be made precise below. This way, the assumption of essential local finiteness becomes part of the characterization.
As a side product, we identify the maximal weight inducing the metric in the case when the path metric space is complete.

Furthermore, as an application we characterize when the resistance metric is a path metric induced by the graph structure.




Acknowledgments. Funding through the DFG is acknowledged by the authors.



 §.§ Set-up and definitions



Throughout the  article, let X be a countable set whose elements are called vertices. We define the path space of X via

    Π(X) := {γ: {0,…,n}→ X   |    n ∈_0, γ}

and the space of infinite paths of X via

    Π_∞ (X):= {γ: _0 → X   |  γ}.

We identify paths  in Π(X) (or Π_∞(X)) with (γ(0),…,γ(n)) (or   with (γ(0),γ(1),…)). For γ = (x_0,…,x_n) ∈Π(X), we say γ is a path from x_0 to x_n.





	 We call a function w:X× X → [0,∞] a weight function  on X if w is symmetric, i.e., w(x,y)=w(y,x) for all x,y ∈ X, and zero on and only on the diagonal, i.e., w(x,y)=0 if and only if x=y for x,y ∈ X. 

Every weight w on X induces a pseudo metric δ_w:X× X → [0,∞] on X via

    δ_w(x,y) := inf{∑_i=1^n w(x_i-1,x_i) | (x_0,…,x_n)  x  y  } .

A pseudo metric is a symmetric map that is zero on the diagonal and satisfies the triangle inequality. In contrast to a metric we allow for the value ∞ and do not ask for definiteness.

Observe that δ_w ≤ w (i.e., δ_w(x,y) ≤ w(x,y) for all x,y∈ X) for all weights w. Let δ be a pseudo metric on X. A weight w on X is said to generate δ if δ = δ_w.
It is not hard to see from the triangle inequality that every pseudo metric δ is also a weight and δ_δ=δ. A pseudo metric δ is said to be discrete if (X,δ) is a discrete  space.


A weight function is called locally finite if for all x ∈ X we have #{y∈ X | w(x,y) < ∞} < ∞ . The following weaker notion of local finiteness is crucial for the considerations of this paper.

[Essential local finiteness]
A weight function is called essentially locally finite if 
for all x ∈ X and all R>0

    #{y∈ X | w(x,y) <R} < ∞ .
 

For a weight w and γ=(x_0,…,x_n) ∈Π(X), we denote the w-length by 
    l_w(γ) :=∑_i=1^n w(x_i-1,x_i).

Similarly, for γ=(x_0,x_1,… ) ∈Π_∞(X),  we set  l_w(γ) :=∑_i=1^∞ w(x_i-1,x_i).


A  w-geodesic is a path γ∈Π(X)  from x to y such that 

    l_w(γ)= δ_w(x,y).

An infinite path γ=(x_0,x_1,…) ∈Π_∞ (X) is called a w-geodesic from x_0 if  (x_0,…,x_n) is w-geodesic for all n ∈.
Observe that every w-geodesic is δ_w-geodesic. 
A weight w is  geodesically complete if l_w(γ)=∞  for all infinite w-geodesics γ. 


For a given pseudo metric space (X,δ), we write for short, l:=l_δ and call every δ-geodesic a geodesic.  A pseudo metric space (X,δ) is called geodesically complete if l(γ) = ∞ for all infinite geodesics γ.
For a pseudo metric space (X,δ), we introduce the geodesic weight w_δ via

    w_δ(x,y) :=  δ(x,y)     (x,y)  x  y  
    ∞   .

Finally, given a pseudo metric  on X we denote the distance balls for x∈ X and R≥ 0 by

B_R(x):={y∈ X|(x,y)≤ R}.







§ THE HOPF-RINOW THEOREM


The Hopf-Rinow theorem below is the main result of the paper.

 
	Let (X,δ) be a pseudo metric space. Then, there exists a weight generating δ. Let w be such a weight. Then the following statements are equivalent:
	
		
  (i) #B_R(x) < ∞ for all x ∈ X and R>0.
		
		
		
  (ii) The space (X,δ) is complete and w is essentially locally finite.
		
  (iii) The space (X,δ) is geodesically complete and the geodesic weight w_δ is essentially locally finite.
		
  (iv) The weight w is geodesically complete and  essentially locally finite.
	
	If one of these conditions holds, then  is discrete and   for any x,y∈ X, there exists a w-geodesic. Furthermore, 
	
    w_δ(x,y) = sup{w(x,y)|δ_w = δ},

	x,y ∈ X and w_δ generates δ.


We start the proof with a basic lemma which shows that essential local finiteness implies discreteness.

 
	Let w be an essentially locally finite weight on X. Then, δ_w is discrete. 


Let x ∈ X. Since #{y∈ X| w(x,y) < 1} < ∞ and w vanishes only on the diagonal, there exists >0 such that w(x,y) > for all y ∈ X.
Let y ∈ X, let n ∈ and let (x_0,…,x_n) be a path from x to y. Then, ∑_i=1^n w(x_i-1,x_i) ≥ w(x,x_1) >.
Hence, δ_w(x,y) ≥ and thus, B_/2(x) = {x}. Since x was chosen arbitrary, this implies discreteness of (X,δ).


The next lemma shows another consequence of essential local finiteness. Specifically, every infinite set of finite paths with bounded lengths gives rise to an infinite path of bounded length.

  
	
	Let w be an essentially locally finite weight on X generating a metric δ=δ_w, let x ∈ X and let R>0.  Let 𝒫⊆{γ∈Π(X)|γ(0) = x, l_w(γ) < R} be an infinite set of finite paths with fixed starting point and bounded w-length. Then, there exists an infinite path γ_∞∈Π_∞(X) such that for every n∈ there exist infinitely many paths γ∈𝒫 with γ(k)=γ_∞(k), for k=0,…,n, and l_w(γ_∞) ≤ R.



 Due to countabilty, we can assume wellordering of X without applying the axiom of choice, and thus, every non-empty subset of X possesses a minimum.

We define γ_∞ inductively starting with _∞(0)=x and

    γ_∞(n+1) :=  min{y ∈ X|#{γ∈𝒫_n |γ(n+1)=y } =∞}

for n∈  with

    𝒫_n :=  {γ∈𝒫|γ(i) = γ_∞(i)  i=0,…,n },

whenever the set from which the minimum is taken is non-empty. Indeed, this is always the case as we show now: 

We know that the set of vertices which occur in paths of 𝒫 is finite  since w(γ(i-1),γ(i)) < R for all γ∈𝒫 and since w is essentially locally finite. But  every partition of an infinite set into finitely many subsets has an infinite subset.
This implies the existence of some y such that there are infinitely many paths in 𝒫 starting with (γ_∞(0),…,γ_∞(n),y) under the assumption of the existence of infinitely many paths in 𝒫  starting with (γ_∞(0),…,γ_∞(n)). By induction, we obtain that for every n∈, there exist infinitely many paths in 𝒫 starting with (γ_∞(0),…,γ_∞(n)). Since the w-length of all paths in 𝒫 is upper bounded by R, we conclude l_w(γ_∞) ≤ R.


 
	Let w be an essentially locally finite weight on X such that (X,δ_w) is complete. Then, for all x,y ∈ X, there exists a w-geodesic from x to y.



Let x,y ∈ X. Suppose, there is no w-geodesic from x to y. Then l_w(γ)>δ_w(x,y) for all paths γ from x to y. But there is a sequence of paths (γ_i) with l_w(γ_i) ⟶δ_w(x,y) as i →∞.
Hence, 

    𝒫 :={γ∈Π(X) | x y  l_w(γ) < δ_w(x,y)+1}

satisfies #𝒫 = ∞. 
Now,  Lemma <ref>  yields the existence of an infinite path γ_∞ with finite w-length l_w(γ_∞) ≤δ_w(x,y) + 1.  This implies that γ_∞ is a Cauchy-sequence. Due to completeness, γ_∞ converges to some limit in X which is not a discrete point since _∞ is injective. This is a contradiction to Lemma <ref> and thus, there exists a w-geodesic from x to y.





	Let w be an essentially locally finite weight on X which is geodesically complete. Then, for every x,y∈ X there is a w-geodesic from x to y.

Let x,y∈ X such that x≠ y. Our aim is to find a w-geodesic from x to y. 
	To this end, let ( _j) be a sequence of paths from x to y such that
	
    lim_j→∞l_w( _j)=(x,y).


	
	Let 𝒫:={γ_j | j ∈}.
	
	If #𝒫 < ∞, then 𝒫 obviously contains a w-gedeosic from x to y.
	
	If #𝒫 = ∞, then by Lemma <ref> there is an infinite path _∞ such that for every n∈, there exist infinitely many _j such that _j(k)=γ_∞(k) for all k=0,…,n. We fix n∈ and let >0. 
	Then, there exists _j  such that _j(k)=γ_∞(k) for all k=0,…,n and l_w(_j) ≤(x,y)+.
	
	
	
	 We estimate
	 
    (x,y)   ≤(_∞(0),_∞(n))+(_∞(n),y)
       ≤  l_w((_∞(0),…,_∞(n)))+(_∞(n),y)
       ≤ l_w(_j)
       ≤(x,y)+.

	 Letting → 0, we see that all inequalities turn into equalities and, therefore,
	 
    (_∞(0),_∞(n))= l_w((_∞(0),…,_∞(n))).

	 
	 
	 Hence, _∞ is a w-geodesic which has finite length. This contradicts the assumption of w-geodesic completeness.





The existence of a weight w that generates δ follows from δ_δ=δ. Let w be such a weight.

	(i) ⇒ (ii). 	
The space  (X,δ) is complete since all balls are complete due to finiteness.
Since #B_R(x) < ∞ for all x ∈ X and R>0 and w ≥δ_w = δ, the weight w is essentially locally finite.
 

	(ii) ⇒ (iii). 
We first show geodesic completeness.	
Suppose not. Then, there is an infinite geodesic γ=(x_0,x_1,…) with l(γ) < R for some R>0.
Then, γ is a Cauchy sequence converging to some x∈ X due to completeness. But since γ is injective, this implies that x is not a discrete point. This is a contradiction to Lemma <ref>. Hence, X is geodesically complete.


Next, we show w_δ(x,y) ≥ w(x,y) for all x,y ∈ X.
Let x,y ∈ X. Due to Lemma <ref>, there exists a w-geodesic (x_0,…,x_n) from x=x_0 to y=x_n. If n=1 then w(x,y)=δ(x,y)  and if 
 n≥2 then w_δ(x,y)=∞. Thus, w_δ(x,y)∈{w(x,y),∞} which proves  w_δ(x,y) ≥ w(x,y). We infer 
    #{y∈ X| w_δ(x,y) <R}≤#{y∈ X| w(x,y) <R} < ∞
 for all R>0 by essential local finiteness of w which is assumed in (ii). This proves essential local finiteness of w_δ.

	(iii) ⇒ (i). 
First, we show that w_δ generates δ.  
To do so, we show that for all x ≠ y, there exists a maximal δ-geodesic γ =(x_0,…,x_n) from x to y in the sense that (x_i,x_i-1) is the only geodesic between x_i and x_i-1 for i=1,…,n.
Suppose not. 
Then, there is a sequence of geodesics γ_k: {0,…,k}→ X such that (γ_k) ⊂(γ_k+1) for k≥ 1 where we denote the range of a function f:A → B by (f):=f(A).
The map 
    Φ: Γ := ⋃_k∈ (γ_k) → [0, δ(x,y)],     z ↦(x,z)
 is isometric since all γ_k are geodesics. Since #Γ = ∞, the range (Φ) has an accumulation point due to the Bolzano-Weierstrass theorem and there exists a strictly monotone sequence (r_k )  in (Φ) converging to this accumulation point. Hence, (Φ^-1(r_k) )_k=0^∞ is an infinite geodesic of finite length. This is a contradiction to geodesic completeness and thus, there exists  a maximal δ-geodesic γ = (x_0,…,x_n) from x to y.
Moreover, maximality implies w_δ(x_i,x_i-1) = δ(x_i,x_i-1) for i=1,…,n and thus, l_w_δ(γ) = δ(x,y). Consequently, w_δ generates δ since x and y were chosen arbitrarily. Moreover, for every x,y ∈ X, there exists a w_δ-geodesic between x and y.
	
	
Next, we prove #B_R(x) < ∞ for all x ∈ X and R>0.	
Suppose  # B_R(x) = ∞ for some R>0, x∈ X. 
Then, there are infinitely many w_δ-geodesics γ starting from x with w_δ-length l_w_δ (γ) ≤ R since there exists a w_δ-geodesic between x and y for all y. Thus, we can apply Lemma <ref>,and hence, there exists an infinite path γ_∞ with l_w_δ(γ_∞) ≤ R such that (γ_∞(0),…,γ_∞(n)) is w_δ-geodesic for all n. Consequently, γ_∞ is an infinite geodesic with finite length. This is a contradiction to geodesic completeness.


(ii) ∧ (iii) ⇒ (iv): Essential local finiteness of w is immediate by (ii). Since every w-geodesic is a _w-geodesic, we infer that geodesic completeness assumed in (iii) implies  w-geodesic completeness. 


(iv) ⇒ (ii): By Lemma <ref> for every x,y∈ X there exists a w-geodesic from x to y. So, for any Cauchy-sequence (x_k)  there are geodesics _k from x_0 to x_k. If (x_k) does not admit a limit, then the set of these geodesics 𝒫 :={_k} is infinite. Moreover,  (x_k) is bounded as a Cauchy-sequence, so, there exists an infinite w-geodesic by Lemma <ref> of finite length. This contradicts the geodesic completeness of w.


Lemma <ref> implies discreteness of δ and Lemma<ref> or Lemma <ref> show the existence of paths.


We still have to prove w_δ(x,y) = sup{w(x,y)|δ_w = δ} for all x,y ∈ X. 
In the proof of (i) ⇒ (ii) we have already shown that w is essentially locally finite if w generates δ. Moreover, we showed
 w≤ w_δ for all essentially locally finite w which generate δ in (ii) ⇒ (iii). Furthermore, we have proven that w_δ generates δ in (iii) ⇒ (i). Putting these three observations together, we obtain w_δ(x,y) = sup{w(x,y)|δ_w = δ}.  This finishes the proof.	



§ RESISTANCE METRIC

In this section we show that for a graph the resistance metric is a path metric induced by the graph structure if and only if  the graph is a block graph. Moreover, we can even characterize when the resistance metric is a path metric induced by the inverse edge weights.


Let b be a graph over a discrete set X which is a symmetric map b:X× X→[0,∞) with zero diagonal that satisfies

    ∑_y∈ Xb(x,y)<∞,     x∈ X.

Let C(X) be the real valued functions and let  Q:C(X)→[0,∞], 

    Q(f) := 1/2∑_x,y∈ X b(x,y)(f(x)-f(y))^2=∑_x∈ XΓ(f)(x),

where

    Γ(f)(x):= 1/2∑_y∈ X b(x,y)(f(x)-f(y))^2,     x∈ X.





The following proposition is well known and can be shown by standard arguments found in <cit.>.

[Resistance metric]
The map R on X× X given by

    R(x,y) := sup{(f(y)-f(x))^2  |   Q(f) = 1 }= sup_f:X→(f(y)-f(x))^2/Q(f)

for x,y∈ X is a metric. Moreover if b is connected, the supremum in the definition is a unique maximum which is  assumed in a  function which is harmonic outside of x and y, i.e., a function f satisfying Lf(v) := ∑_wb(v,w)(f(v)-f(w))=0 for all v∈ X ∖{x,y }.	

The metric R introduced in the proposition above is called the resistance metric. Furthermore, let _1/b be the path metric generated by the weight 1/b. If b is a tree, see e.g. <cit.>, then

    R=_1/b.

So, it is a natural question whether there are other situations when R is a path metric induced by the graph structure. 

To answer this question, we first characterize sharpness of the triangle inequality of the resistance metric.


	Let b be a graph over X and let x,y,z ∈ X. The following statements are equivalent:
	
		
  (i) R(x,z) = R(x,y) + R(y,z).
		
  (ii) All paths from x to z pass through y.
	 



Without obstruction,	we assume that b is connected.

	(i) ⇒ (ii): We show the implication by contraposition. Let f be a function satisfying Q(f)=1 and (f(x)-f(z))^2=R(x,z) and f(x)>f(z). Then, f(x)>f(y)>f(z).
	We write
	f_x:= f ∨ f(y) and f_z:=f ∧ f(y). By Young's inequality and since 1=Q(f) ≥ Q(f_x) + Q(f_y), we have
	
    (f_x(x) - f_x(y))^2/Q(f_x) + 	
    	(f_z(z) - f_z(y))^2/Q(f_z)≥(f(x) - f(z))^2/Q(f_x) + Q(f_z)≥ R(x,z).

	By definition, we have
	R(x,y) ≥(f_x(x) - f_x(y))^2/Q(f_x) and
	R(y,z) ≥(f_z(z) - f_z(y))^2/Q(f_z).
	Suppose there is a path from x to z not passing through y. Then, there are vertices v,w∈ X with b(v,w)>0 on this path such that f(v) > f(y)≥ f(w) and y ≠ w. 	
	Applying Proposition <ref> gives  Lf(w) = 0 and thus,
	Lf_z(w) = Lf(w) + b(v,w)(f(v) - f(y)) ≠ 0, implying
     R(y,z) > (f_z(z) - f_z(y))^2/Q(f_z). Consequently,
	
    R(x,y)+R(y,z)  
    	>     (f_x(x) - f_x(y))^2/Q(f_x) + 	
    	(f_z(z) - f_z(y))^2/Q(f_z)≥  R(x,z).


	
	(ii) ⇒ (i): Let x,y,z∈ X. Assume every path from x to z passes through y.
	We define
	
    S_x:={w∈ X ∖{y}| x  w  y}.

	Since every path from x to z passes through y, we have
	
    S_x={w∈ X ∖{y}:  z  w  y}.

	Analogously, we define
	
    S_z    :={w∈ X ∖{y}:  z  w  y}
       = {w∈ X ∖{y}:  x  w  y}.

	Hence, 
    S_x∩ S_z = ∅        
    	b(S_x× S_z) =0,
 i.e., b(v,w)=0 for all v∈ S_x,w∈ S_z.
	Obviously, x ∈ S_x and z ∈ S_z.
	
	We take a function f_x such that. Q(f_x)=1 and f_x(y)=0 and f_x(x)^2=R(x,y) and f_x(x)>0. Analogously, we take a function
	f_z, such that  Q(f_z)=1 and f_z(y)=0 and f(z)^2=R(z,y) and f_z(z)>0.
	
	We claim that (f_x) ⊂ S_x.
	To prove the claim, we set f_x:=f_x · 1_S_x and observe that it suffices to show Q(f_x)≤ Q(f_x) due to uniqueness of the minimizer following from Proposition <ref>. To this end, observe that every neighbor of w ∈ S_x is either in S_x or y. Since f_x(y)=0 we infer
		
    Γ (f_x)(w)    = Γ( f_x)(w),     w ∈ S_x.

		Moreover, since  S_x∩ S_z = ∅ and  b(S_x× S_z) = 0 we have f_x=0 on S_z and all neighbors of vertices in S_z. Thus,
		
    Γ (f_x)(w)    = 0,     w ∈ S_z

		Finally, on all neighbors of y in S_x the functions f_x and f_x agree, for all other neighboring vertices w we have (f_x(y)-f_x(w))^2=0 and, hence,
	
    Γ (f_x)(y)    ≤Γ (f_x)(y).

	Thus, Q(f_x)≤ Q(f_x) and, therefore, (f_x) ⊂ S_x.  
	Analogously, one shows   (f_z) ⊂ S_z.	As a consequence the function
	
    f:=  1/√(f_x(x)^2+f_z(z)^2)(f_x(x) f_x- f_z(z)f_z)
 
	satisfies 
	
    Q(f)= 1/f_x(x)^2+f_z(z)^2(f_x(x)^2 Q(f_x)+ f_z(z)^2Q(f_z)=1

	and, therefore, since we have
	 f(x)=f_x(x)^2/ √(f_x(x)^2+f_z(z)^2) and  f(z)=-f_z(z)^2/ √(f_x(x)^2+f_z(z)^2), we obtain
	
    R(x,y)≥ (f(x)-f(z))^2
    	=f_x(x)^2+f_z(z)^2=R(x,y)+R(y,z).

	Since R satisfies the triangle inequality statement (i) follows.



	Let b be a connected graph over X. The following statements are equivalent:
	
		
  (i) R=_1/b
		
  (ii) b is a tree.
	


(ii) ⟹ (i): This follows from the theorem above or <cit.> (see the arxiv version for a detailed proof).

(i) ⟹ (ii): Assume there exists a cycle. Let x be a vertex on this cycle. Denote by C the set of all neighbors y of x such that the edge (x,y) is contained in a cycle. Since b is summable about x there exists y∈ C such that b(x,y) is the maximum of b(x,·) on C. Then,  d_1/b(x,y)=1/b(x,y). Moreover, any function f on X such that f(x)=1 and f(y)=0 satisfies Q(f)≥ b(x,y) and, therefore, R(x,y)≥_1/b(x,y). 
In order to achieve equality, we need that such a function f satisfies  f(v)=f(w) for all v,w∈ X  with b(v,w)>0 and {x,y}≠{v,w}. This however, is impossible as the edge (x,y) is contained in a cycle.



In the above corollary, we can also weaken the assumption R=δ_1/b by only requiring that the weight is supported only on the edges.
We say a weight w is compatible to a graph b if w(x,y) = ∞ whenever b(x,y)=0 and x ≠ y.
It turns out that the existence of a compatible weight inducing the resistance metric is related to block graphs, i.e., graphs where any two vertices are connected by a unique induced path.



	Let b be a locally finite graph over X.
Then, the following statements are equivalent:

	
  (i) R=_w for some w compatible to b.
	
  (ii) The graph b is a block graph.
	



(ii) ⟹ (i):
We choose 
    w(x,y)=
    R(x,y)   : x∼ y x=y
    ∞   :otherwise.

By triangle inequality, δ_w ≥ R. Moreover, δ_w(x,y) = R(x,y) if x∼ y.
It remains to show δ_w(x,y) ≤ R(x,y) for non-adjacent x,y.
Let (x_0,…,x_n) be the unique induced path from x to y.
Then, every path from x to y must pass through all x_i for i=0,…, n.
Thus, we can apply Theorem <ref> to conclude

    R(x,y)=∑_i=1^n R(x_i,x_x-1)= ∑_i=1^n w(x_i,x_x-1) ≥δ_w(x,y)

which proves R=w_.

(ii) ⟹ (i):
We assume that R=δ_w for some w compatible to the graph.
Let x ≠ y ∈ X.
We aim to show that there is a unique induced path from x to y.
We distinguish two cases.

Case one: There is a w-geodesic (x_0,…,x_n) from x to y.
Suppose there exists an induced path γ≠ (x_0,…,x_n) from x to y.
Then, there exists i ∈{0,… n} such that  γ does not pass through x_i.
Hence by Theorem <ref>,
R(x,y) < R(x,x_i) + R(x_i,y). But this is a contradiction to the fact that  (x_0,…,x_n) is a geodesic. So in the first case, there exists a unique induced path from x to y.

Case two: There is no w-geodesic from x to y.
Then, there exists a sequence of paths γ_n from x to y with l_w(γ_n) → R(x,y) as n →∞.
By local finiteness and by Lemma <ref>, there exists an infinite path γ_∞ such that  for all k ∈ there exists n ∈ such that  γ_n(i)=γ_∞(i) for i=0,…, k.
Then, γ_∞ is a w-geodesic by triangle inequality.
Let k be large such that  γ_1 does not pass through γ_∞(k-1).
Let γ_n be a path such that  γ_∞(i)=γ_n(i) for all i ≤ k.
Let 
    W:= (γ_1) ∪ ( (γ_n) ∖{γ_∞(0),…, γ_∞(k-1)}).

Then as a union of paths sharing the vertex y, the by W induced subgraph is connected. Hence, there exists a path from x to γ_∞(k) within W. Observe, γ_∞(k-1) ∉ W.
Thus, by Theorem <ref>,
R(x,γ_∞(k))< R(x,γ_∞(k-1)) + R(γ_∞(k-1),γ_∞(k)).
But this is a contradiction to the fact that γ_∞ is a geodesic.
Hence, the second case can not occur.
The complete case distinction finishes the proof.



alpha
	


