# Note on intrinsic metrics on graphs

Daniel Lenz  Institut für Mathematik, Friedrich-Schiller-Universität Jena,
07743 Jena, Germany<EMAIL_ADDRESS>,  Marcel Schmidt
Mathematisches Institut, Universität Leipzig, 04109 Leipzig, Germany.
<EMAIL_ADDRESS>and  Felix Seifert  Institut für
Mathematik, Friedrich-Schiller-Universität Jena, 07743 Jena, Germany.
<EMAIL_ADDRESS>
###### Abstract.

We study the set of intrinsic metrics on a given graph. This is a convex
compact set and it carries a natural order. We investigate existence of
largest elements with respect to this order. We show that the only locally
finite graphs which admit a largest intrinsic metric are certain finite star
graphs. In particular all infinite locally finite graphs do not admit a
largest intrinsic metric. Moreover, we give a characterization for the
existence of intrinsic metrics with finite balls for weakly spherically
symmetric graphs.

##  1\. Introduction

Analysis of the Laplace-Beltrami operator on a Riemannian manifold is
intimately linked to the geometry of the manifold. Of particular importance is
the metric geometry with respect to the geodesic distance, see e.g. [5] for a
survey. In his seminal works [14, 15, 16] Sturm realized that many theorems
which hold on Riemannian manifolds can also be established for operators
induced by strongly local Dirichlet forms when one replaces the geodesic
distance by so-called intrinsic metrics. On such Dirichlet spaces there is the
notion of a measure valued gradient, which we denote by $\Gamma$. On a
Riemannian manifold it is given by $\Gamma(f)=|\nabla f|^{2}{\rm dvol}$. The
characterizing property of an intrinsic metric $\varrho$ is a Rademacher type
result: If $f$ is $1$-Lipschtiz with respect to $\varrho$, then $\Gamma(f)\leq
1$ (this notation means that the Radon-Nikdoym derivative with respect to the
underlying measure is $\leq 1$). It turns out that there is a largest
intrinsic metric $\kappa$, which is given by

$\displaystyle\kappa(x,y)$ $\displaystyle=\sup\\{|f(x)-f(y)|\mid f\text{
continuous with }\Gamma(f)\leq 1\\}$
$\displaystyle=\sup\\{\varrho(x,y)\mid\varrho\text{ intrinsic}\\}.$

In the Riemannian setting this metric coincides with the geodesic distance.

One assumption that is usually needed in the analysis of the corresponding
operators is compactness of balls with respect to an intrinsic metric. Since
large metrics lead to smaller balls and in view of the Riemannian case, it
therefore makes sense to view $\kappa$ as the canonical intrinsic metric of
the strongly local Dirichlet space. In fact, the metric $\kappa$ is exactly
the metric that the mentioned works of Sturm rely on.

In recent years there was an increased interest in analysis of unbounded graph
Laplacians and more general non-local operators. It was noted that the
combinatorial graph distance is not well suited for many analytical problems
on graphs and, therefore, metrics adapted to the situation were introduced
simultaneously by several authors, see [2, 3] for graphs specifically, and
[13] and [6] for some more general non-local operators and [4] for a treatment
of arbitrary regular Dirichlet forms. The setting of [4] includes the Laplace-
Beltrami operator, operators of strongly local Dirichlet forms, graph
Laplacians and more general non-local operators. Intrinsic metrics have since
been successfully applied to tackle various analytical problems, see e.g. the
survey [9] and the more recent book [11] for a comprehensive overview in the
discrete case.

It was noted already in [4] that in non-local situations the maximum of two
intrinsic metrics need not be intrinsic, which led to the observation that in
general there is no largest intrinsic metric. This is a notable difference
between the strongly local situation and the situation of non-local operators.
Now, the considerations in [4] provide just one example of a graph for which
no maximal intrinsic metric exists. So, they naturally raise the question
wether examples of graphs admitting maximal intrinsic metrics exist at all or
whether the non-existence of a maximal intrinsic metric is a - so to speak -
characteristic feature of the non-locality.

In this paper we give a complete answer to this question for locally finite
graphs. Such a graph possesses a largest intrinsic metric if and only if it is
a star graphs satisfying some condition on the measure, see Theorem 3.5. So,
if one assumes local finiteness, only for very few specific finite graphs a
largest intrinsic metric exists. In particular, largest intrinsic metrics can
not exist for infinite locally finite graphs. In this sense lack of a largest
intrinsic metric is a characteristic feature of non-locality in the infinite
situation.

For graphs that are not locally finite we do not have a comprehensive answer
because in this case non-trivial intrinsic metrics need not exist, see Example
2.5. We discuss some partial results after Proposition 3.4.

As mentioned above, for analysis of the graph Laplacian it is desirable to
have intrinsic metrics with relatively small balls, which means large
intrinsic metrics. Even if there is no largest intrinsic metric, one can still
ask for maximal intrinsic metrics (in the sense of maximal elements with
respect to the pointwise order on intrinsic metrics). It turns out that
maximal intrinsic metrics always exist due to some compactness of the set of
all intrinsic metrics, see Proposition 3.7, but they are not unique if there
is no largest intrinsic metric (i.e. in the locally finite situation the graph
is not a star graph), see Theorem 3.8.

Summarizing Theorem 3.5 and Theorem 3.8 one can say that - up to a few
specific exceptions given by certain finite graphs - locally finite graphs do
not admit canonical intrinsic metrics.

The related question whether a given graph possesses an intrinsic metric with
finite balls is hard to answer in general. There are only two abstract
criteria in this direction: For locally finite graphs and path metrics there
is a Hopf-Rinow type result, namely a path metric has finite balls if and only
if it is complete, see [8, Appendix A]. Also on locally finite graphs it was
recently noted that the existence of an intrinsic metric with finite balls is
related to the existence of a sequence of cut-off functions, see [12, Appendix
A]. The latter property is also known as $\chi$-completeness and was
characterized in [1] for radially symmetric trees. In Section 4 we extend this
to weakly spherically symmetric graphs, which were introduced in [10]. We can
characterize when intrinsic metrics with finite balls and an additional
symmetry conditions exist. Under some growth condition on the measure, this
symmetry condition on the metric can be dropped, see Theorem 4.1. In
particular, we obtain a sharp criterion for the existence of intrinsic metrics
with finite balls on antitrees with polynomially growing spheres, see Example
4.3.

Section 3 grew out of the Bachelor’s thesis of the third named author.

Acknowledgements. D. L. and M. S. gratefully acknowledge partial support of
German Research Foundation (DFG).

##  2\. Set up and (non) existence of nontrivial intrinsic metrics

Let $X\neq\emptyset$ be a countable set equipped with the discrete topology.
Hence, any function on $X$ is continuous, a subset of $X$ is compact if and
only if it is finite and the $\sigma$-algebra generated from the open sets
consists just of all subsets. The space of bounded real-valued functions on
$X$ is denoted by $\ell^{\infty}(X)$ and we write $C(X)$ for all real-valued
functions on $X$. Due to $X$ being discrete the support of $f\in C(X)$ is
given by ${\rm supp}f=\\{x\in X\mid f(x)\neq 0\\}$ and we write $C_{c}(X)$ for
all real valued functions of finite support. We write $s\wedge t$ and $s\vee
t$ for the minimum and maximum of the real numbers $s$ and $t$ respectively.
We extend this to functions $f,g\in C(X)$ pointwisely.

Let $m\colon X\to(0,\infty)$. We abuse notation and also view $m$ as a measure
on all subsets of $X$ by

$m(A)=\sum_{x\in A}m(x),\quad A\subseteq X.$

A weighted graph on $X$ is a symmetric function $b\colon X\times
X\to[0,\infty)$ such that $b(x,x)=0$ for all $x\in X$ and such that the
weighted vertex degree satisfies

$\deg(x):=\sum_{y\in X}b(x,y)<\infty$

for each $x\in X$.

Two points $x,y\in X$ are said to be connected by an edge if $b(x,y)>0$. In
this case, we write $x\sim y$. The graph $b$ is called locally finite if for
each $x\in X$ the set of its neighbors

$\\{y\in X\mid x\sim y\\}$

is finite. In this case, we write $N(x):=|\\{y\in X\mid x\sim y\\}|$. A path
is a finite sequence $\gamma=(x_{0},\ldots,x_{n})$ in $X$ with $x_{0}\sim
x_{1}\sim\ldots\sim x_{n}$. We say it connects $x$ and $y$ if they are
contained in the path. The graph $b$ is called connected if all $x,y\in X$ are
connected by a path.

A pseudo metric on $X$ is a symmetric function $\sigma\colon X\times
X\to[0,\infty)$ satisfying the triangle inequality. It is called intrinsic
with respect to $b$ and $m$ if

$\frac{1}{m(x)}\sum_{y\in X}b(x,y)\sigma(x,y)^{2}\leq 1$

for every $x\in X$. We write $\mathfrak{M}=\mathfrak{M}_{b,m}$ for the set of
all intrinsic pseudo metrics with respect to $b$ and $m$.

In applications the most important feature of intrinsic pseudo metrics is the
following Rademacher type result: If $\sigma$ is an intrinsic pseudo metric
and $f\colon X\to{\mathbb{R}}$ is $L$-Lipschitz with respect to $\sigma$ (i.e.
$|f(x)-f(y)|\leq L\sigma(x,y)$ for all $x,y\in X$), then

$|\nabla f|:=\left(\frac{1}{m(x)}\sum_{y\in
X}b(x,y)|f(x)-f(y)|^{2}\right)^{1/2}\leq L.$

Clearly, the trivial pseudo metric $\sigma=0$ is always an intrinsic pseudo
metric and so the first question is whether non-trivial intrinsic metrics
always exist. The following example provides a positive answer for locally
finite (connected) graphs.

######  Example 2.1 (Path pseudo metrics).

Assume the graph $b$ is connected and let $w\colon X\times X\to[0,\infty)$. To
a path $\gamma=(x_{0},\ldots,x_{n})$ we associate its length (with respect to
$w$) by

$L_{w}(\gamma)=\sum_{k=1}^{n}w(x_{k-1},x_{k})\wedge w(x_{k},x_{k-1}).$

The function

$d_{w}\colon X\times
X\to[0,\infty),\,d_{w}(x,y)=\inf\\{L_{w}(\gamma)\mid\gamma\text{ path
connecting }x\text{ and }y\\}$

is called the path pseudo metric induced by the weight $w$. It is readily
verified that $d_{w}$ is a pseudo metric. Note that $d_{w}$ only depends on
the values $w(x,y)$ with $x\sim y$. Hence, in some examples below we only
specify the values of such $w$ on neighbors. Note also that we can assume
without loss of generality that $w$ is symmetric (i.e. satisfies
$w(x,y)=w(y,x)$ for all $x,y\in X$ with $x\sim y$) as we could otherwise
replace it by the symmetric $w(x,y)\wedge w(y,x)$.

Path pseudo metrics have the following characteristic feature.

######  Proposition 2.2 (Characterisation of path pseudo metrics).

Let $(X,b)$ be a connected graph. Let $\varrho$ be a pseudo metric on $X$.

(a) If $\varrho$ is a path pseudo metric induced by the weight $w$, then any
pseudometric $\sigma$ with $\sigma(x,y)\leq w(x,y)$ for all $x,y\in X$ with
$x\sim y$ satisfies $\sigma\leq\varrho$.

(b) The pseudometric $\varrho$ is a path pseudo metric if and only if any
pseudometric $\sigma$ with $\sigma(x,y)\leq\varrho(x,y)$ for all $x,y\in X$
with $x\sim y$ satisfies $\sigma\leq\varrho$.

###### Proof.

(a) Assume without loss of generality that $w$ is symmetric. Let $x,y\in X$ be
given and $(x_{0},\ldots,x_{n})$ a path connecting $x$ and $y$. Then, the
triangle inequality (for $\sigma$) gives

$\sigma(x,y)\leq\sum_{k=1}^{n}\sigma(x_{k-1},x_{k})\leq\sum_{k=1}^{n}w(x_{k-1},x_{k}).$

Taking the infimum over all path connecting $x$ and $y$ we find
$\sigma\leq\varrho$.

(b) From (a) we easily infer the ’only if’ part. To show the ’if’ part assume
that $\varrho$ has the feature that any pseudometric $\sigma$ with
$\sigma(x,y)\leq\varrho(x,y)$ for all $x,y\in X$ with $x\sim y$ satisfies
$\sigma\leq\varrho$. Consider now the pseudo path metric
$\sigma:=d_{\varrho}$. Then, clearly $\sigma(x,y)\leq\varrho(x,y)$ holds for
all $x,y\in X$ with $x\sim y$. So, we infer

$\sigma\leq\varrho.$

Moreover, as $\varrho$ is a pseudo metric we can apply the triangle inequality
to $\varrho$ to find for any path $(x_{0},\ldots,x_{n})$ connecting $x$ and
$y$ that

$\varrho(x,y)\leq\sum_{k=1}^{n}\varrho(x_{k-1},x_{k})$

holds. Taking the infimum over all path we obtain

$\varrho\leq d_{\varrho}=\sigma.$

Putting this together we find that $\varrho=d_{\varrho}$ is a path metric. ∎

If the graph is locally finite and $w(x,y)>0$ for all $x\sim y$, then $d_{w}$
is even a metric inducing the discrete topology on $X$. For $w=1$ the metric
$d:=d_{1}$ is called combinatorial distance, as it counts the least number of
edges in a path connecting $x,y$.

The path pseudo metric $d_{w}$ satisfies $d_{w}(x,y)\leq w(x,y)\wedge w(y,x)$
for $x\sim y$. Hence, it is intrinsic if

$\frac{1}{m(x)}\sum_{y\in X}b(x,y)w(x,y)^{2}\leq 1.$

One function $w$ satisfying this inequality is given by

$w(x,y)=\frac{m(x)^{1/2}}{\deg(x)^{1/2}}\wedge\frac{m(y)^{1/2}}{\deg(y)^{1/2}}.$

This provides a concrete example of an intrinsic pseudo metric that is a path
pseudo metric.

The combinatorial distance $d$ satisfies $d(x,y)=1$ for $x\sim y$. Hence, it
is intrinsic if and only if $\deg/m$ is bounded by $1$.

Another class of intrinsic pseudo metrics is induced by functions on $X$. This
is discussed next.

######  Example 2.3 (Intrinsic metrics induced by functions).

Let $f\colon X\to\mathbb{R}$. Then

$\sigma_{f}\colon X\times X\to[0,\infty),\quad\sigma_{f}(x,y)=|f(x)-f(y)|$

is obviously a pseudo metric on $X$. It is intrinsic if and only if $|\nabla
f|\leq 1$. Moreover, it is a metric if and only if $f$ is injective.

The following lemma introduces a metric which dominates all intrinsic pseudo
metrics. It leads to examples of graphs that do not possesses any nontrivial
intrinsic pseudo metric and to compactness of the set of all intrinsic pseudo
metrics $\mathfrak{M}$ with respect to pointwise convergence.

######  Lemma 2.4.

Let $(X,b)$ be a graph and consider $s\colon X\times X\to[0,\infty)$ with

$s(x,y)=\frac{m(y)^{1/2}}{b(x,y)^{1/2}}$

for $x\sim y.$ Then any intrinsic pseudo metric $\sigma$ satisfies $\sigma\leq
d_{s}$. In particular, $\sigma(x,y)\leq s(x,y)$ for $x\sim y$.

###### Proof.

Let $\sigma$ be intrinsic. For $z\sim x$ the inequality $\sum_{y\in
X}b(x,y)\sigma(x,y)^{2}\leq m(x)$ implies

$\sigma(x,z)\leq\frac{m(x)^{1/2}}{b(x,z)^{1/2}}=s(z,x)$

where we use the symmetry of $b$ to obtain the last equality. As $\sigma$ is a
metric this gives

$\sigma(x,y)=\sigma(y,x)\leq s(x,y)$

whenever $x\sim y$ holds. From (a) of Proposition 2.2 we then infer
$\sigma\leq d_{s}$. ∎

######  Example 2.5 (Graphs without nontrivial intrinsic pseudo metric).

Assume

$\inf_{z\in
X}\left(\frac{m(z)^{1/2}}{b(x,z)^{1/2}}+\frac{m(z)^{1/2}}{b(y,z)^{1/2}}\right)=0$

for all $x,y\in X$ (here we use the convention
$m(z)^{1/2}/b(x,z)^{1/2}=\infty$ if $x\not\sim z$). Then the triangle
inequality and the previous lemma imply that there is no nontrivial intrinsic
pseudo metric with respect to $b$ and $m$. In this case, Example 2.3 shows
that any $f\in C(X)$ with $|\nabla f|\in\ell^{\infty}$ is constant, which is a
quite remarkable property.

We now explicitly construct such a graph. We let $X={\mathbb{N}}$,

$b\colon{\mathbb{N}}\times{\mathbb{N}}\to[0,\infty),\quad
b(i,j)=\begin{cases}\frac{1}{i^{2}+j^{2}}&\text{if }i\neq j\\\ 0&\text{if
}i=j\end{cases}$

and

$m\colon{\mathbb{N}}\to(0,\infty),\quad m(i)=\frac{1}{i^{3}}.$

It is clear that $b$ is symmetric and satisfies the summability condition.
Moreover,

$\frac{m(k)^{1/2}}{b(i,k)^{1/2}}+\frac{m(k)^{1/2}}{b(j,k)^{1/2}}=\frac{(i^{2}+k^{2})^{1/2}}{k^{3/2}}+\frac{(j^{2}+k^{2})^{1/2}}{k^{3/2}}\rightarrow
0,\quad k\rightarrow\infty,$

which shows that $({\mathbb{N}},b)$ has no nontrivial intrinsic metric with
respect to $m$.

######  Remark.

Non-existence of nontrivial intrinsic pseudo metrics is not a special feature
of graphs or non-local operators. Indeed, for certain strongly local Dirichlet
forms on fractals the measures $\Gamma(f)$ mentioned in the introduction are
always singular to the underlying measure and hence the only intrinsic pseudo
metric is the trivial one, see e.g. [7].

######  Proposition 2.6.

Let $b$ be a graph over $(X,m)$. Then $\mathfrak{M}$ is a compact convex
subset of $C(X\times X)$ equipped with the topology of pointwise convergence.

###### Proof.

The convexity of $\mathfrak{M}$ follows directly from the the definition of
intrinsic pseudo metrics and the convexity of the function
$[0,\infty)\to[0,\infty),\,x\mapsto x^{2}$.

Since $X\times X$ is at most countable, the topology of pointwise convergence
on $C(X\times X)$ is metrizable. Let $d_{s}$ be the metric introduced in Lemma
2.4. By a standard diagonal sequence argument the set

$\\{f\in C(X\times X)\mid 0\leq f\leq d_{s}\\}$

is compact in $C(X\times X)$ with respect to pointwise convergence. By Lemma
2.4 it contains $\mathfrak{M}$ and so it suffices to show that $\mathfrak{M}$
is closed. Let $(\sigma_{n})$ in $\mathfrak{M}$ and $\sigma\in C(X\times X)$
with $\sigma_{n}\to\sigma$ pointwise. The pointwise limit of pseudo metrics is
clearly a pseudo metric and Fatou’s lemma yields

$\sum_{y\in X}b(x,y)\sigma(x,y)^{2}\leq\liminf_{n\to\infty}\sum_{y\in
X}b(x,y)\sigma_{n}(x,y)^{2}\leq m(x)$

for all $x\in X$. Hence, $\sigma\in\mathfrak{M}$. ∎

Clearly, the set $C(X\times X)$ carries a natural order $\leq$ with $F\leq G$
if $F(x,y)\leq G(x,y)$ for all $x,y\in X$. This order induces an order on
$\mathfrak{M}$ and we look for largest elements with respect to this order.
This is the topic of the next section.

##  3\. Maximal intrinsic metrics

As mentioned in the introduction intrinsic pseudo metrics with small balls are
useful in applications. Small balls correspond to large pseudo metrics. Hence,
we study largest intrinsic pseudo metrics in this section. Here, largest
refers to the natural order structure on the set of intrinsic metrics induced
by pointwise comparison (compare discussion at the end of previous section).

One candidate for a largest intrinsic pseudo metric is the pointwise sup of
all intrinsic metrics. For connected locally finite graphs it turns out that
only on special star graphs this leads to an intrinsic metric (Theorem 3.5).

In the quest for largest intrinsic metrics one may also turn to maximal
intrinsic metrics (i.e. intrinsic metrics $\sigma$ which agree with any
intrinsic metric $\varrho$ with $\sigma\leq\varrho$). Such maximal intrinsic
metrics can be shown to exist on any graph with the help of Zorn’s lemma
(Proposition 3.7). However, except in the case of the special star graphs
already mentioned, there will exist more than one such maximal intrinsic
metric (Theorem 3.8). So, there is a lack of uniqueness.

Let $b$ be a graph over $(X,m)$. From Lemma 2.4 we infer that the function

$\kappa=\kappa_{b,m}=\sup\\{\sigma\mid\sigma\in\mathfrak{M}_{b,m}\\}$

is finite with $\kappa\leq d_{s}$. As a pointwise supremum of pseudo metrics
it is a pseudo metric itself. We call it the canonical pseudo metric of $b$
over $(X,m)$. If the graph is locally finite, there are intrinsic metrics (cf.
Example 2.1) and so $\kappa$ is indeed a metric in this case.

######  Proposition 3.1.

Let $b$ be a graph over $(X,m)$. For $x,y\in X$ we have

$\kappa(x,y)=\sup\\{|f(x)-f(y)|\mid f\in C(X)\text{ with }´|\nabla f|\leq
1\\}.$

###### Proof.

Let $S_{xy}=\sup\\{|f(x)-f(y)|\mid|\nabla f|\leq 1\\}$. As noted in Example
2.3 for $f\in C(X)$ with $|\nabla f|\leq 1$ the pseudo metric $\sigma_{f}$ is
intrinsic. Since $\sigma_{f}(x,y)=|f(x)-f(y)|$, this leads to $\kappa(x,y)\geq
S_{xy}$.

Now let $\sigma$ be an intrinsic pseudo metric. For $w\in X$ the function
$f_{w}=\sigma(\cdot,w)$ is $1$-Lipschitz and therefore satisfies $|\nabla
f_{w}|\leq 1$. For $x,y\in X$ we obtain
$\sigma(x,y)=\sup\\{|f_{w}(x)-f_{w}(y)|\mid w\in X\\}$. Combining both
observations leads to $S_{xy}\geq\sigma(x,y)$. Since $\sigma$ was arbitrary,
this leads to $\kappa(x,y)\leq S_{xy}$. ∎

######  Definition 3.2 (Star graph).

We say a graph $b$ over $X$ is a star graph if it is connected and there
exists $p\in X$ such that $N(x)=1$ for all $x\in X\setminus\\{p\\}$. In this
case, $p$ is called center of $b$.

A graph $b$ over $X$ is called a galaxy if all of its connected components are
star graphs.

######  Remark.

By definition star graphs are connected. Hence, if $p$ is a center, then every
vertex from $X\setminus\\{p\\}$ is connected to $p$. The center of a star
graph is unique if $|X|\geq 3$.

######  Proposition 3.3.

Let $b$ be a star graph over $(X,m)$. The following assertions are equivalent.

  1. (i)

The canonical pseudo metric $\kappa$ is intrinsic.

  2. (ii)

There exists a center $p\in X$ of $b$ such that

$\sum_{x\in X\setminus\\{p\\}}m(x)\leq m(p).$

###### Proof.

Let $p\in X$ be a center of $b$. If $X=\\{p\\}$, then there is nothing to show
and we therefore assume $|X|\geq 2$. We first prove

$\kappa(x,p)^{2}=\frac{m(x)\wedge m(p)}{b(x,p)}$

for $x\in X\setminus\\{p\\}$. We already know from Lemma 2.4 that the left
hand side is smaller than the right hand side.

For the opposite inequality for $x\in X\setminus\\{p\\}$ we consider the
function

${f=\left(\frac{(m(x)\wedge
m(p))^{\frac{1}{2}}}{b(x,p)^{\frac{1}{2}}}\right)1_{\\{x\\}}}.$

Using that $b$ is a star graph with center $p$, it is readily verified that
$|\nabla f|\leq 1$. Hence, the discussion in Example 2.3 shows that
$\sigma_{f}$ is an intrinsic pseudo metric. Since

$\sigma_{f}(x,p)^{2}=(f(x)-f(p))^{2}=\frac{m(x)\wedge m(p)}{b(x,p)}$

and since $\kappa$ is the supremum over all intrinsic pseudo metrics, we
obtain the desired equality.

If $x\in X\setminus\\{p\\}$, our formula for $\kappa$ shows

$\frac{1}{m(x)}\sum_{y\in
X}b(x,y)\kappa(x,y)^{2}=\frac{b(x,p)}{m(x)}\frac{m(x)\wedge m(p)}{b(x,p)}\leq
1.$

In particular, $\kappa$ being intrinsic can only fail at $p$. But at $p$ we
have

$\frac{1}{m(p)}\sum_{y\in X}b(p,y)\kappa(p,y)^{2}=\frac{1}{m(p)}\sum_{y\in
X\setminus\\{p\\}}(m(y)\wedge m(p)).$

It is readily verified that this sum is $\leq 1$ if and only if $\sum_{y\in
X\setminus\\{p\\}}m(y)\leq m(p)$. This shows the equivalence of (i) and (ii).
∎

######  Proposition 3.4.

Let $b$ be a locally finite connected graph over $(X,m)$ and assume it is not
a star graph. Then $\kappa$ is not intrinsic.

###### Proof.

We assume that $\kappa$ is intrinsic and construct another intrinsic pseudo
metric which is larger than $\kappa$ in one argument. Since $b$ is connected
but no star graph, there exist $x,y\in X$ with $x\sim y$ and $N(x),N(y)\geq
2$. Using that $b$ is locally finite we can assume without loss of generality
that $y$ satisfies

$\kappa(x,y)=\min\\{\kappa(x,z)\mid z\sim x\text{ and }N(z)\geq 2\\}.$

Moreover, local finiteness implies that $\kappa$ is a metric and we obtain

$s:=\min(\\{\kappa(x,z)\mid z\sim x\\}\cup\\{\kappa(y,z)\mid z\sim y\\})>0.$

By our choice of $s$ and since $\kappa$ is intrinsic, there exists
$0<\varepsilon<s/3$ with

$\frac{1}{m(x)}\left(\sum\limits_{z\in
X\setminus\\{y\\}}b(x,z)(k(x,z)-\frac{s}{3})^{2}+b(x,y)(k(x,y)+\varepsilon)^{2}\right)\leq
1$

and

$\frac{1}{m(y)}\left(\sum\limits_{z\in
X\setminus\\{x\\}}b(y,z)(k(y,z)-\frac{s}{3})^{2}+b(y,x)(k(y,x)+\varepsilon)^{2}\right)\leq
1.$

Next we consider the weight

$w=\kappa+\varepsilon 1_{C}-\frac{s}{3}1_{D},$

with $C=\\{x,y\\}\times\\{x,y\\}$ and
$D=\\{x,y\\}\times(X\setminus\\{x,y\\})\cup(X\setminus\\{x,y\\})\times\\{x,y\\}$.
The above inequalities and $\kappa$ being intrinsic yield

$\frac{1}{m(u)}\sum_{z\in X}b(u,z)w(u,z)^{2}\leq 1$

for all $u\in X$. Hence, the induced path metric $d_{w}$ is intrinsic.

We finish the proof by showing $d_{w}(x,y)\geq\kappa(x,y)+\varepsilon$. Let
$\gamma=(x_{0},\ldots,x_{n})$ be a path connecting $x$ and $y$. Assume without
loss of generality that the $x_{j}$, $j=1,\ldots,n$, are pairwise different.
We prove $L_{w}(\gamma)\geq\kappa(x,y)+\varepsilon$.

If $n=1$, then $x_{0}=x,x_{1}=y$ and we obtain

$L_{w}(\gamma)=w(x,y)=\kappa(x,y)+\varepsilon.$

If $n\geq 2$, without loss of generality we can assume $N(x_{i})\geq 2$ for
all $i=1,\ldots,n-1$ (otherwise $(x_{0},\ldots x_{i-1},x_{i+1},\ldots,x_{n})$
is a shorter path connecting $x$ and $y$). In particular, we then have
$N(x_{1})\geq 2$.

Now, by the very definition of path we have $x_{1}\neq x,x_{n-1}\neq y$ and -
as the elements of the path are pairwise different - we also have $x_{1}\neq
y$ and $x_{n-1}\neq x$. So, $(x,x_{1})$ and $(x_{n-1},y)$ both belong to $D$.
Hence, we obtain

$\displaystyle L_{w}(\gamma)\geq
w(x,x_{1})+w(x_{n-1},y)=\kappa(x,x_{1})-\frac{s}{3}+\kappa(x_{n-1},y)-\frac{s}{3}.$

The definition of $s$ yields $\kappa(x_{n-1},y)\geq s$. Our choice of $y$
(together with $N(x_{1})\geq 2$) yields $\kappa(x,x_{1})\geq\kappa(x,y)$.
Altogether we arrive at

$L_{w}(\gamma)\geq\kappa(x,y)+\frac{s}{3}\geq\kappa(x,y)+\varepsilon,$

where we used $\varepsilon<s/3$ in the last estimate. ∎

######  Remark.

Example 2.5 shows that the previous proposition does not hold in general on
graphs that are not locally finite. The graph without nontrivial intrinsic
pseudo metric constructed there is a complete graph (every vertex is connected
to every other vertex). Note however that the previous proposition holds true
(with essentially the same proof) under weaker conditions. One only needs the
existence of $x\in X$ with $2\leq N(x)<\infty$ and $N(z)<\infty$ for all
$z\sim x$ and the existence of $y\sim x$ with $N(y)\geq 2$. In other words,
the combinatorial $2$-ball around $x$ is locally finite and the graph is not a
star graph.

######  Theorem 3.5.

Let $b$ be a connected locally finite graph over $(X,m)$. The following
assertions are equivalent.

  1. (i)

The canonical metric $\kappa$ is intrinsic.

  2. (ii)

$b$ is a star graph with center $p\in X$ such that

$\sum_{x\in X\setminus\\{p\\}}m(x)\leq m(p).$

###### Proof.

(i) $\Rightarrow$ (ii): It follows from Proposition 3.4 that $\kappa$ is not
intrinsic if $b$ is not a star graph. The criterion on $m$ follows Proposition
3.3.

(ii) $\Rightarrow$ (i): This follows from Proposition 3.3. ∎

######  Remark.

We formulated the theorem for connected graphs but it also holds on locally
finite non-connected graphs. In this case, $\kappa$ is an intrinsic metric if
and only if $b$ is a galaxy and the inequality in (ii) holds on each of its
stars (i.e. every connected component).

Next we discuss how $\kappa$ being intrinsic is related to uniqueness of
maximal intrinsic pseudo metrics. To this end, we need a finitary description
of $\kappa$ being intrinsic as given by the next proposition.

######  Proposition 3.6.

Let $b$ be a graph over $(X,m)$. The following assertions are equivalent.

  1. (i)

$\kappa$ is an intrinsic metric.

  2. (ii)

For all intrinsic metrics $\varrho,\sigma$ the metric $\varrho\vee\sigma$ is
intrinsic.

###### Proof.

(i) $\Rightarrow$ (ii): If $\varrho,\sigma$ are intrinsic, then
$\varrho,\sigma\leq\kappa$, which implies $\varrho\vee\sigma\leq\kappa$. Since
$\kappa$ is intrinsic, this implies that $\varrho\vee\sigma$ is intrinsic.

(ii) $\Rightarrow$ (i): Since $X\times X$ is countable, we find a sequence
$(\sigma_{n})$ in $\mathfrak{M}$ with

$\kappa=\sup\\{\sigma_{n}\mid
n\in{\mathbb{N}}\\}=\lim_{N\to\infty}\sup\\{\sigma_{n}\mid 1\leq n\leq N\\},$

where the convergence holds pointwise. Iterating the assumption yields
$\sup\\{\sigma_{n}\mid 1\leq n\leq N\\}\in\mathfrak{M}$. Since $\mathfrak{M}$
is closed with respect to pointwise convergence, we arrive at (i). ∎

Even though $\kappa$ may not be an intrinsic metric there always exist maximal
intrinsic pseudo metrics. More precisely, an intrinsic pseudo metric $\sigma$
is called maximal if for any other intrinsic pseudo metric $\varrho$ the
inequality $\sigma(x,y)\leq\varrho(x,y)$ for all $x,y\in X$ implies
$\varrho=\sigma$.

######  Proposition 3.7 (Existence of maximal intrinsic metrics).

Let $b$ be a graph over $(X,m)$. For every intrinsic pseudo metric $\sigma$
there exists a maximal intrinsic pseudo metric $\varrho$ with
$\sigma\leq\varrho$.

###### Proof.

We use Zorn’s lemma. The pointwise order on

$\mathfrak{M}_{\sigma}:=\\{\varrho\mid\varrho\in\mathfrak{M}\text{ with
}\sigma\leq\varrho\\}$

is a partial order. Let $\mathfrak{F}\subseteq\mathfrak{M}_{\sigma}$ be a
totally ordered subset. We show that $\mathfrak{F}$ has an upper bound in
$\mathfrak{M}_{\sigma}$.

Since $X\times X$ is countable, there exists a sequence $(\varrho_{n})$ in
$\mathfrak{F}$ with

$\sup\\{\varrho_{n}\mid
n\in{\mathbb{N}}\\}=\sup\\{\varrho\mid\varrho\in\mathfrak{F}\\}.$

Since $\mathfrak{F}$ is totally ordered, for every $n\in{\mathbb{N}}$ we have
$\varrho_{n}\leq\varrho_{n+1}$ or $\varrho_{n}\geq\varrho_{n+1}$. We use this
to inductively define $r_{1}=\varrho_{1}$ and for $n\geq 2$

$r_{n}=\begin{cases}\varrho_{n}&\text{if }r_{n-1}<\varrho_{n}\\\
r_{n-1}&\text{if }r_{n-1}\geq\varrho_{n}\end{cases}.$

Then $r_{n}\in\mathfrak{F}$, $r_{n}\leq r_{n+1}$ and $\varrho_{n}\leq r_{n}$.
We infer

$\sup\\{\varrho\mid\varrho\in\mathfrak{F}\\}=\sup\\{\varrho_{n}\mid
n\in{\mathbb{N}}\\}=\sup\\{r_{n}\mid
n\in{\mathbb{N}}\\}=\lim_{n\to\infty}r_{n},$

where the limit holds pointwise. By Proposition 2.6 pointwise limits of
intrinsic pseudo metrics are again intrinsic pseudo metrics. Hence,
$\sup\\{\varrho\mid\varrho\in\mathfrak{F}\\}\in\mathfrak{M}_{\sigma}$ is an
upper bound for $\mathfrak{F}$. ∎

The fact that in general $\kappa$ is not an intrinsic metric leads to non-
uniqueness of maximal intrinsic metrics.

######  Theorem 3.8.

Let $b$ be a locally finite connected graph over $(X,m)$. The following
assertions are equivalent.

  1. (i)

There exists a unique maximal intrinsic metric.

  2. (ii)

$b$ is a star graph and it has a center $p\in X$ such that

$\sum_{x\in X\setminus\\{p\\}}m(x)\leq m(p).$

###### Proof.

(ii) $\Rightarrow$ (i): By Theorem 3.5 assertion (ii) implies that $\kappa$ is
an intrinsic metric. Clearly it is maximal.

(i) $\Rightarrow$ (ii): Assume (ii) does not hold. According to Proposition
3.6 and Theorem 3.5 there exist intrinsic pseudo metrics $\varrho,\sigma$ such
that $\varrho\vee\sigma$ is not intrinsic. By Proposition 3.7 we can assume
that $\varrho$ and $\sigma$ are maximal. Since $\varrho\vee\sigma$ is not
intrinsic, we infer $\varrho\neq\sigma$. ∎

For certain examples non-uniqueness of maximal intrinsic pseudo metrics can be
seen quite easily.

######  Example 3.9.

Consider $X=\mathbb{Z}$ with $b(n,m)=1$ if $|n-m|=1$ and $b(n,m)=0$, else.
Moreover, let $m(n)=1$, $n\in{\mathbb{Z}}$, be the counting measure. For any
function $f\colon{\mathbb{Z}}\to{\mathbb{R}}$ with

$1=|\nabla f|^{2}(n)=(f(n+1)-f(n))^{2}+(f(n-1)-f(n))^{2}$

for all $n\in{\mathbb{Z}}$ the pseudo metric $\sigma_{f}$ is maximal
intrinsic. Clearly, there are many such functions on $\mathbb{Z}$.

##  4\. Existence of intrinsic pseudo metrics with finite balls

In this section we (partially) characterize when weakly spherically symmetric
graphs (see below for a definition) admit intrinsic pseudo metrics with finite
balls. To this end we employ a criterion involving existence of certain cut-
off functions.

A weighted graph $b$ over $(X,m)$ is called $\chi$-complete if there exists a
sequence $(\chi_{n})$ in $C_{c}(X)$ with $\chi_{n}\to 1$ pointwise and $C>0$
such that

$|\nabla\chi_{n}|\leq C$

for all $n\in{\mathbb{N}}$. In this case, we simply call $(\chi_{n})$ a
sequence of cut-off functions for $b$ over $(X,m)$. Let
$T\colon{\mathbb{R}}\to{\mathbb{R}},T(x)=(x\wedge 1)\vee 0$. Then $T$ is
$1$-Lipschitz and therefore $|\nabla(T\circ\chi_{n})|\leq|\nabla\chi_{n}|\leq
C$. Hence, we may always assume that cut-off functions satisfy
$0\leq\chi_{n}\leq 1$. It was recently proven in [12] that a locally finite
graph $b$ over $(X,m)$ is $\chi$-complete if and only if there exists an
intrinsic pseudo metric with finite balls.

From now on we assume that the graph $b$ over $(X,m)$ is connected. Recall
that $d$ is the combinatorial graph metric. Fix $o\in X$. We say that a
function $f\colon X\to{\mathbb{R}}$ is radially symmetric with respect to $o$
if the value $f(x)$ only depends on $d(x,o)$. In this case, given $x\in X$
with $d(x,o)=r$ we abuse notation and write $f(r)$ for the value $f(x)$. Often
$o$ is fixed and we simply say that $f$ is radially symmetric.

A graph $b$ over $(X,m)$ is called weakly spherically symmetric if there
exists $o\in X$ (the root) such that the functions $\kappa_{\pm}\colon
X\to{\mathbb{R}}$ defined by

$\kappa_{\pm}(x)=\frac{1}{m(x)}\sum_{y\in S_{r\pm 1}}b(x,y),\quad\text{if
}x\in S_{r},$

are radially symmetric. Here, $S_{r}=\\{x\in X\mid d(x,o)=r\\}$ denotes the
combinatorial $r$-sphere around $o$ if $r\in\mathbb{N}_{0}$¸ and we use the
convention $S_{-1}=\emptyset$, which leads to $\kappa_{-}(o)=0$. In this case,
for radially symmetric $f\colon X\to{\mathbb{R}}$ the function $|\nabla
f|^{2}$ is also radially symmetric and for $r\geq 1$ it takes the form

$\displaystyle|\nabla f|^{2}(r)$
$\displaystyle=\kappa_{-}(r)(f(r)-f(r-1))^{2}+\kappa_{+}(r)(f(r)-f(r+1))^{2}$
$\displaystyle=\frac{1}{m(S_{r})}\kappa_{+}(r-1)m(S_{r-1})(f(r)-f(r-1))^{2}$
$\displaystyle\quad+\frac{1}{m(S_{r})}\kappa_{+}(r)m(S_{r})(f(r)-f(r+1))^{2}.$

For the second equality we used
$\kappa_{+}(r)m(S_{r})=\kappa_{-}(r+1)m(S_{r+1})$, which follows from

$\kappa_{+}(r)m(S_{r})=\sum_{x\in S_{r},y\in
S_{r+1}}b(x,y)=\kappa_{-}(r+1)m(S_{r+1}).$

This quantity can be interpreted as the weighted size of the combinatorial
boundary of $B_{r}=\\{x\in X\mid d(x,o)\leq r\\}$, which is why we write
$|\partial B_{r}|=\kappa_{+}(r)m(S_{r})$. Hence, the formula for the gradient
reads

$|\nabla f|^{2}(r)=\frac{1}{m(S_{r})}\left(|\partial
B_{r-1}|(f(r)-f(r-1))^{2}+|\partial B_{r}|(f(r)-f(r+1))^{2}\right).$

######  Theorem 4.1.

Let $b$ be a locally finite and weakly spherically symmetric graph over
$(X,m)$ with root $o\in X$. Of the following assertions (i), (ii) and (iii)
are equivalent, (i)/(ii)/(iii) implies (iv) and (iv) implies (v).

  1. (i)

The graph is $\chi$-complete and there exists a sequence of cut-off functions
which are radially symmetric.

  2. (ii)

There exists an intrinsic pseudo metric with finite balls $\sigma$ such that
the function $\sigma(o,\cdot)$ is radially symmetric.

  3. (iii)

$\sum_{r=1}^{\infty}\frac{\sqrt{m(S_{r})\wedge m(S_{r+1})}}{\sqrt{|\partial
B_{r}|}}=\infty.$

  4. (iv)

There exists an intrinsic metric with finite balls.

  5. (v)

$\sum_{r=1}^{\infty}\frac{\sqrt{m(S_{r})}}{\sqrt{|\partial
B_{r}|}}=\sum_{r=1}^{\infty}\frac{1}{\sqrt{\kappa_{+}(r)}}=\infty.$

If, moreover, there exists $K>0$ such that $m(S_{r})\leq Km(S_{r+1})$ for all
$r\geq 1$, then all assertions are equivalent.

###### Proof.

(i) $\Rightarrow$ (ii): That the existence of a sequence of cut-off functions
yields an intrinsic pseudometric with finite balls was shown in [12, Theorem
A.1]. Here we discuss why the pseudometric constructed in the proof of [12,
Theorem A.1] is radially symmetric.

Let $(\psi_{n})$ be a sequence of cut-off functions which are radially
symmetric. As seen in the proof of the implication (iii) $\Rightarrow$ (i) of
[12, Theorem A.1], there is a sequence of cut-off functions $(\varphi_{n})$
with the following properties:

  * •

Every $\varphi_{n}$ is a convex combination of finitely many of the functions
$\psi_{n},n\in{\mathbb{N}}$.

  * •

$|\nabla\varphi_{n}|\to 0$ uniformly, as $n\to\infty$.

The first property implies that $\varphi_{n}$ is radially symmetric and the
second yields that we can assume without loss of generality (after possibly
passing to a suitable subsequence)

$\sum_{n=1}^{\infty}\left\||\nabla\varphi_{n}|\right\|_{\infty}\leq 1.$

Moreover, since $\varphi_{n}\to 1$ pointwise, we can also assume (after
passing to another subsequence)

$\sum_{n=1}^{\infty}(1-\varphi_{n}(x))^{2}<\infty$

for all $x\in X$. Under these conditions it is shown in the proof of [12,
Theorem A.1] that $\sigma\colon X\times X\to[0,\infty)$ given by

$\sigma(x,y)=\left(\sum_{n=1}^{\infty}(\varphi_{n}(x)-\varphi_{n}(y))^{2}\right)^{1/2}$

is an intrinsic metric with finite balls. Clearly, the function
$\sigma(o,\cdot)$ is radially symmetric because the functions
$\varphi_{n},n\in{\mathbb{N}},$ are radially symmetric.

(ii) $\Rightarrow$ (i): The functions

$\chi_{n}\colon X\to[0,\infty),\quad\chi_{n}(x)=(1-\sigma(o,x)/n)_{+}$

are radially symmetric and satisfy $|\nabla\chi_{n}|\leq 1/n$ because $\sigma$
is intrinsic, see e.g. [11, Proposition 11.29]. Their support is contained in
the ball $B^{\sigma}_{n}(o)$, which is finite by assumption, and they satisfy
$\psi_{n}\to 1$ pointwise.

(i) $\Rightarrow$ (iii): Let $(\psi_{n})$ be a sequence of cut-off functions
which are radially symmetric. Then there exists $C\geq 0$ such that for all
$r,n\in{\mathbb{N}}$ we have

$\kappa_{-}(r)(\psi_{n}(r)-\psi_{n}(r-1))^{2}+\kappa_{+}(r)(\psi_{n}(r)-\psi_{n}(r+1))^{2}=|\nabla\psi_{n}|^{2}(r)\leq
C.$

This implies

$(\psi_{n}(r)-\psi_{n}(r+1))^{2}\leq
C\left(\frac{1}{\kappa_{+}(r)}\wedge\frac{1}{\kappa_{-}(r+1)}\right)=C\frac{m(S_{r})\wedge
m(S_{r+1})}{|\partial B_{r}|}.$

For a given $R\geq 1$ we choose $n\in{\mathbb{N}}$ large enough such that
$\psi_{n}(R)\geq 1/2$. Since $\psi_{n}$ has finite support, there is $l\geq 1$
such that $\psi_{n}(r)=0$ for $r\geq R+l$. These properties of $\psi_{n}$
yield

$\displaystyle\frac{1}{2}$
$\displaystyle\leq|\psi_{n}(R)-\psi_{n}(R+l)|\leq\sum_{r=R}^{R+l-1}|\psi_{n}(r)-\psi_{n}(r+1)|$
$\displaystyle\leq\sqrt{C}\sum_{r=R}^{\infty}\frac{\sqrt{m(S_{r})\wedge
m(S_{r+1})}}{\sqrt{|\partial B_{r}|}}.$

Since $R$ was arbitrary, we arrive at (ii).

(iii) $\Rightarrow$ (i): We consider radially symmetric functions $\chi_{n}$
defined by $\chi_{n}(o)=1$ and, for $r\geq 1$,

$\chi_{n}(r)=\left(1-\sum_{k=0}^{r-1}1_{[n,\infty)}(k)\frac{\sqrt{m(S_{k})\wedge
m(S_{k+1})}}{\sqrt{|\partial B_{k}|}}\right)_{+}.$

Clearly, $\chi_{n}\to 1$ pointwise and

$\displaystyle|\chi_{n}(r)-\chi_{n}(r+1)|^{2}$
$\displaystyle\leq\frac{m(S_{r})\wedge m(S_{r+1})}{|\partial B_{r}|}.$

The latter inequality and our expression for $|\nabla\chi_{n}|^{2}$ in the
radially symmetric case yield $|\nabla\chi_{n}|^{2}\leq 2$. The assumption
(ii) implies that $\chi_{n}$ has compact support and we arrive at (i).

(ii) $\Rightarrow$ (iv): This is trivial

(iv) $\Rightarrow$ (v): As discussed in [12, Theorem A.1] the existence of an
intrinsic pseudo metric with finite balls yields a sequence of cut-off
functions $(\chi_{n})$ and we assume $0\leq\chi_{n}\leq 1$. We consider
radially symmetric functions $\varphi_{n}$ defined as follows. First we
inductively choose a sequence $(x_{r})$ with $x_{0}=o$ and $x_{r}\in S_{r}$
such that

$|\chi_{n}(x_{r})-\chi_{n}(x_{r-1})|=\min\\{|\chi_{n}(y)-\chi_{n}(x_{r-1})|\mid
y\sim x_{r-1},y\in S_{r}\\},$

and then we set $\varphi_{n}(r)=\chi_{n}(x_{r})$. Clearly, $\varphi_{n}$ has
finite support and $\varphi_{n}\to 1$ pointwise. Moreover, for $r\geq 1$ we
obtain by our choice of $x_{r}$

$\displaystyle\kappa_{+}(r)(\varphi_{n}(r)-\varphi_{n}(r+1))^{2}$
$\displaystyle=\frac{1}{m(x_{r})}\sum_{y\in
S_{r+1}}b(x,y)(\chi_{n}(x_{r})-\chi_{n}(x_{r+1}))^{2}$
$\displaystyle\leq\frac{1}{m(x_{r})}\sum_{y\in
S_{r+1}}b(x,y)(\chi_{n}(x_{r})-\chi_{n}(y))^{2}$
$\displaystyle\leq|\nabla\chi_{n}|^{2}(x_{r})\leq C.$

This implies

$(\varphi_{n}(r)-\varphi_{n}(r+1))^{2}\leq
C\frac{1}{\kappa_{+}(r)}=C\frac{m(S_{r})}{|\partial B_{r}|}.$

With this at hand we can argue as in the proof of (i) $\Rightarrow$ (ii) to
conclude (iv).

If we assume $m(S_{r})\leq Km(S_{r+1})$ for all $r\geq 0$, the equivalence of
(ii) and (v) is obvious. ∎

######  Remark.

It remains open whether on any weakly spherically symmetric $\chi$-complete
graph the sequence of cut-off functions can be chosen to be radially
symmetric. Note that the sequence $(\varphi_{n})$ constructed in the proof of
(iv) $\Rightarrow$ (v) need not be a sequence of cut-off functions. They
satisfy

$\kappa_{+}(r)(\varphi_{n}(r)-\varphi_{n}(r+1))^{2}\leq C$

but only the weaker bound

$\displaystyle\kappa_{-}(r)(\varphi_{n}(r)-\varphi_{n}(r-1))^{2}$
$\displaystyle=\frac{m(S_{r-1})}{m(S_{r})}\kappa_{+}(r-1)(\varphi_{n}(r)-\varphi_{n}(r-1))^{2}$
$\displaystyle\leq C\frac{m(S_{r-1})}{m(S_{r})},$

which leads to

$|\nabla\varphi_{n}|^{2}(r)\leq C\left(1+\frac{m(S_{r-1})}{m(S_{r})}\right).$

Hence, $(\varphi_{n})$ is a sequence of cut-off functions if there exists
$K>0$ such that $m(S_{r})\leq Km(S_{r+1})$ for all $r\geq 0$, which is the
additional condition in the theorem.

######  Remark.

The idea for the proof of implication (iii) $\Rightarrow$ (i) is taken from
the proof of [1, Theorem 3.20].

Let $D\subseteq[0,\infty)$. For functions $f,g\colon D\to(0,\infty)$ we write
$f\sim g$ if there exists $C>0$ such that $C^{-1}f(t)\leq g(t)\leq Cf(t)$ for
all sufficiently large $t\in D$. If $m$ satisfies $m(S_{\cdot})\sim f$ for
some monotone increasing function $f\colon{\mathbb{N}}\to(0,\infty)$, then
there exists $K\geq 0$ such that $m(S_{r})\leq Km(S_{r+1})$ for all
$r\in{\mathbb{N}}$. In this case, all assertions of Theorem 4.1 are
equivalent.

######  Example 4.2 (Trees).

Let $m=1$ be the counting measure on $X$ and let be an infinite radially
symmetric connected tree with $b\in\\{0,1\\}$. Then $m(S_{n})=|S_{n}|$ and
since any $y\in S_{r+1}$ has exactly one neighbor in $S_{r}$ (this is the
defining property of a connected tree), we have $|\partial B_{r}|=|S_{r+1}|$
and $|S_{r}|\leq|S_{r+1}|$. For the inequality we used that the graph is
radially symmetric and infinite.

Thus, Theorem 4.1 shows that the graph has an intrinsic metric with finite
balls if and only if

$\sum_{r=1}^{\infty}\frac{\sqrt{|S_{r}|}}{\sqrt{|S_{r+1}|}}=\infty.$

This criterion for $\chi$-completeness was obtained in [1, Proposition 3.16].
It shows that if $|S_{r}|$ grows polynomially in $r$, then the graph has an
intrinsic pseudo metric with finite balls. If there exists $\alpha>0$ such
that $|S_{r}|\sim e^{r^{\alpha}}$, then the graph has an intrinsic pseudo
metric with finite balls if and only if $\alpha\leq 1$.

######  Example 4.3 (Antitrees).

Let $X$ be infinite, let $m=1$ be the counting measure and fix $o\in X$. A
connected graph $b$ over $(X,m)$ is called radially symmetric antitree if
every vertex from $S_{n}$ is connected to every vertex from $S_{n+1}$ and
there are no neighbors within $S_{n}$. We assume that $b$ is such an antitree
with $b(x,y)\in\\{0,1\\}$ for all $x,y\in X$. Then $m(S_{n})=|S_{n}|$ and
since every $y\in S_{r+1}$ is connected to all $x\in S_{r}$, we have
$|\partial B_{r}|=|S_{r}||S_{r+1}|$. Hence,

$\sum_{r=1}^{\infty}\frac{1}{\sqrt{|S_{r}|\vee|S_{r+1}|}}=\infty.$

implies that the graph has an intrinsic metric with finite balls. For
$\chi$-completeness this condition was observed in [1, Proposition 3.22].
Moreover, the existence of an intrinsic pseudo metric with finite balls yields

$\sum_{r=1}^{\infty}\frac{1}{\sqrt{|S_{r}|}}=\infty.$

If there exists $\alpha>0$ such that $|S_{r}|\sim r^{\alpha}$, then the
antitree has an intrinsic pseudo metric with finite balls if and only if
$\alpha\leq 2$. Here the ’only if’ part seems to be new.

## References

  * [1] Hatem Baloudi, Sylvain Golénia, and Aref Jeribi.  The adjacency matrix and the discrete Laplacian acting on forms.  Math. Phys. Anal. Geom., 22(1):Paper No. 9, 27, 2019.
  * [2] Matthew Folz.  Gaussian upper bounds for heat kernels of continuous time simple random walks.  Electron. J. Probab., 16:no. 62, 1693–1722, 2011.
  * [3] Matthew Folz.  Volume growth and stochastic completeness of graphs.  Trans. Amer. Math. Soc., 366(4):2089–2119, 2014.
  * [4] Rupert L. Frank, Daniel Lenz, and Daniel Wingert.  Intrinsic metrics for non-local symmetric Dirichlet forms and applications to spectral theory.  J. Funct. Anal., 266(8):4765–4808, 2014.
  * [5] Alexander Grigor′yan.  Analytic and geometric background of recurrence and non-explosion of the Brownian motion on Riemannian manifolds.  Bull. Amer. Math. Soc. (N.S.), 36(2):135–249, 1999.
  * [6] Alexander Grigor’yan, Xueping Huang, and Jun Masamune.  On stochastic completeness of jump processes.  Math. Z., 271(3-4):1211–1239, 2012.
  * [7] Masanori Hino.  On singularity of energy measures on self-similar sets.  Probab. Theory Related Fields, 132(2):265–290, 2005.
  * [8] Xueping Huang, Matthias Keller, Jun Masamune, and Radosław K. Wojciechowski.  A note on self-adjoint extensions of the Laplacian on weighted graphs.  J. Funct. Anal., 265(8):1556–1578, 2013.
  * [9] Matthias Keller.  Intrinsic metrics on graphs: a survey.  In Mathematical technology of networks, volume 128 of Springer Proc. Math. Stat., pages 81–119. Springer, Cham, 2015.
  * [10] Matthias Keller, Daniel Lenz, and Radosław K. Wojciechowski.  Volume growth, spectrum and stochastic completeness of infinite graphs.  Math. Z., 274(3-4):905–932, 2013.
  * [11] Matthias Keller, Daniel Lenz, and Radosław K. Wojciechowski.  Graphs and discrete Dirichlet spaces, volume 358 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer, Cham, [2021] ©2021.
  * [12] Daniel Lenz, Marcel Schmidt, and Melchior Wirth.  Uniqueness of form extensions and domination of semigroups.  J. Funct. Anal., 280(6):Paper No. 108848, 27, 2021.
  * [13] Jun Masamune and Toshihiro Uemura.  Conservation property of symmetric jump processes.  Ann. Inst. Henri Poincaré Probab. Stat., 47(3):650–662, 2011\.
  * [14] Karl-Theodor Sturm.  Analysis on local Dirichlet spaces. I. Recurrence, conservativeness and $L^{p}$-Liouville properties.  J. Reine Angew. Math., 456:173–196, 1994.
  * [15] Karl-Theodor Sturm.  Analysis on local Dirichlet spaces. II. Upper Gaussian estimates for the fundamental solutions of parabolic equations.  Osaka J. Math., 32(2):275–312, 1995.
  * [16] Karl-Theodor Sturm.  Analysis on local Dirichlet spaces. III. The parabolic Harnack inequality.  J. Math. Pures Appl. (9), 75(3):273–297, 1996.