# Recurrent and (strongly) resolvable graphs

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

We develop a new approach to recurrence and the existence of non-constant
harmonic functions on infinite weighted graphs. The approach is based on the
capacity of subsets of metric boundaries with respect to intrinsic metrics.
The main tool is a connection between polar sets in such boundaries and null
sets of paths. This connection relies on suitably diverging functions of
finite energy.

##  1\. Introduction

Potential theory on infinite weighted graphs (sometimes called networks)
studies the induced graph energy functional and derived quantities (e.g.
harmonic functions, random walks, resistances, Laplacians,…). As already noted
in the pioneering works by Yamasaki [27, 16, 28], so-called null sets of
infinite paths play an important role in this theory. For a comprehensive
account of Yamasaki’s work (and beyond) we refer to the book [22].

Another approach to potential theory on weighted graphs is via Dirichlet
forms. The graph energy induces a Dirichlet form, which in turn leads to the
notion of capacity of sets. In this language sets of capacity zero, so-called
polar sets, are key to understanding properties of the Dirichlet form. In
contrast to the situation on graphs, for general Dirichlet forms the concept
of a path may be meaningless. Instead, for many applications it turned out
fruitful to consider intrinsic metrics as geometric input, see e.g. [23, 24,
25, 3, 10].

In this paper we follow the intrinsic metric line of thinking. Our main
observation relates polar sets in certain metric boundaries of graphs to null
sets of paths, see Theorem 3.6. This sheds a new light on classical results
formulated in terms of null sets of paths and allows us to prove new theorems.
In this text we focus on consequences for recurrence and the existence of non-
constant harmonic functions of finite energy:

We prove a new characterization of recurrence in terms of the existence of
intrinsic metrics with finite balls, see Theorem 4.2. This in turn leads to an
alternative proof of a classical characterization of recurrence due to
Yamasaki, see Corollary 4.3 and a characterization of recurrence in terms of
metric boundaries being polar, see Corollary 4.4 and Theorem 4.5.

We then turn to the problem of the existence of non-constant harmonic
functions. Again, we tackle this problem by means of capacity on the boundary.
Specifically, we introduce the notion of strong resolvability, which is
essentially a path-free and capacity-based version of the notion of
resolvability studied in [2]. We show that strongly resolvable transient
graphs admit non-constant harmonic functions of finite energy, see Corollary
5.8 and Corollary 5.9. Since strong resolvability is stronger than
resolvability (this is a consequence of our main observation mentioned
previously), we also prove that locally finite planar graphs of bounded
geometry, the main class of examples of resolvable graphs, are even strongly
resolvable. This allows us to recover one of the main results from [2] that
transient locally finite planar graphs of bounded geometry have non-constant
harmonic functions of finite energy. Note that recently more precise
descriptions of the space of harmonic functions of planar graphs were
obtained, see [1, 5, 9], which are beyond the scope of our theory. Another
consequence of planar graphs of bounded geometry being strongly resolvable is
that they are never canonically compactifiable, see Theorem 6.4. The latter
class of graphs was introduced and studied in [6].

Our results show that two basic issues in the theory of recurrence viz
characterization of recurrence and existence of non-constant harmonic
functions can naturally be understood in terms of capacities of (suitable)
metric boundaries: Recurrence means that metric boundaries are negligible in
the sense of having capacity zero whereas existence of non-constant harmonic
functions is implied by some richness in the structure of such a boundary in
the sense of the positive capacity of the whole boundary not being
concentrated on a single point.

Since our methods do not rely on paths but only on intrinsic metrics, they are
not limited to locally finite graphs as is sometimes the case in the classical
setting. Moreover, they can be adapted to more general Dirichlet spaces and
even non-linear energies. Both directions will be investigated in upcoming
works.

Parts of this text are based on Simon Puchert’s master’s thesis.

Acknowledgments: Partial support of DFG, in particular, within the Priority
programme ’Geometry at infinity’ is gratefully acknowledged.

##  2\. Preliminaries

In this section we introduce the notation and the objects that are used
throughout the text. For $a,b\in{\mathbb{R}}$ we let $a\wedge b=\min\\{a,b\\}$
and $a\vee b=\max\\{a,b\\}$. Moreover, $a_{+}=a\vee 0$ and $a_{-}=(-a)_{+}$.
We extend this notation pointwise to real-valued functions.

###  2.1. Graphs and Dirichlet energy

Our study of graphs is based on an analytic tool given by the Dirichlet
energy.

A _graph_ $G=(X,b)$ consists of a nonempty countable set $X$, whose elements
are called _nodes_ or _vertices_ , and a symmetric _edge weight function_
$b:X\times X\rightarrow[0,\infty)$, satisfying the following conditions: The
edge weight $b$ vanishes on the diagonal, i.e. $b(x,x)=0$ for all $x\in X$,
and the _weighted vertex degree_

$\mathrm{deg}(x):=\sum\limits_{y\in X}b(x,y)$

must be finite for all $x\in X$. If the weighted vertex degree is bounded, we
say that the graph has _bounded geometry_. If the function $b$ takes only
values in $\\{0,1\\}$, the graph $(X,b)$ is called _combinatorial_.

Two vertices $x,y\in X$ are said to be connected by the _edge_ $(x,y)$ if
$b(x,y)>0$. In this case, we write $x\sim y$. Note that since $b$ is
symmetric, we have $x\sim y$ if and only if $y\sim x$. The set of all
(oriented) edges of $G$ is denoted by

$E:=\\{(x,y)\in X\times X\mid x\sim y\\}.$

We say that a graph is _locally finite_ if for all $x\in X$ the set of its
neighbors $\\{y\in X\mid x\sim y\\}$ is finite. A locally finite graph is
called a _bounded valence graph_ if the cardinality of the set of neighbors of
each vertex is bounded by a universal constant.

A _path_ in $G$ is a (finite or infinite) sequence $(x_{1},x_{2},\ldots)$ of
nodes such that $x_{i}\sim x_{i+1}$, for $i=1,2,\ldots$. We say that two
points $x,y\in X$ are connected if there is a finite path
$(x=x_{1},\ldots,x_{n}=y)$. This defines an equivalence relation on the set of
vertices and the resulting equivalence classes are called _connected
components_. From now on we will generally assume that the graph $G$ is
connected without mentioning this explicitly. This is not a real restriction
because all our considerations in this text can be reduced to connected
components.

We equip $X$ with the discrete topology and write $C(X)$ for all real-valued
functions on $X$ (the continuous functions on $X$) and $C_{c}(X)$ for the
finitely supported real-valued functions on $X$ (the continuous functions of
compact support). Any function $m:X\to(0,\infty)$ induces a Radon measure of
full support on all subsets of $X$ via

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

In what follows we do not distinguish between such measures and strictly
positive functions and simply call them _measures_ on $X$.

Every weighted graph $G=(X,b)$ gives rise to a quadratic form $Q\colon
C(X)\rightarrow[0,\infty]$ that assigns to any function $f\colon
X\rightarrow{\mathbb{R}}$ its _Dirichlet energy_

$Q(f):=\frac{1}{2}\sum\limits_{x,y\in X}b(x,y)|f(x)-f(y)|^{2}.$

The space of functions of finite energy is

$\mathfrak{D}(G):=\\{f\colon X\rightarrow\mathbb{R}\mid Q(f)<\infty\\},$

on which $Q$ acts as a bilinear form by polarization, namely

$Q(f,g)=\frac{1}{2}\sum\limits_{x,y\in X}b(x,y)(f(x)-f(y))(g(x)-g(y)).$

Here we abuse notation so that $Q(f)=Q(f,f)$ for every $f\in\mathfrak{D}(G)$.

The form $Q$ has the following fundamental semi-continuity property, which is
a direct consequence of Fatou’s lemma.

######  Proposition 2.1 (Semicontinuity of $Q$).

Let $(X,b)$ be a graph. Let $(f_{n})$ be a sequence of functions on $X$
converging pointwise to the function $f$. Then,

$Q(f)\leq\liminf_{n\to\infty}Q(f_{n}),$

where the value $\infty$ is allowed.

A map $C\colon\mathbb{R}\rightarrow\mathbb{R}$ is called contraction if
$|C(s)-C(t)|\leq|s-t|$ holds for all $s,t\in\mathbb{R}$. The Dirichlet energy
has the important property that it is reduced by contractions. Specifically,
the following proposition is a direct consequence of the definition.

######  Proposition 2.2 (Fundamental contraction property).

Let $(X,b)$ be a graph. For all $f\in\mathfrak{D}(G)$ and all contractions
$C\colon\mathbb{R}\rightarrow\mathbb{R}$ we have $C\circ f\in\mathfrak{D}(G)$
and

$Q(C\circ f)\leq Q(f).$

######  Remark.

Two useful families of contractions that will be of use later are the
following: For $a,b\in{\mathbb{R}}$ we define the _clamping function_
$C_{[a,b]}\colon{\mathbb{R}}\to{\mathbb{R}}$ by

$C_{[a,b]}(x):=(x\wedge b)\vee a$

and for $c\in{\mathbb{R}}$ we define the _slicing function_
$S_{c}\colon{\mathbb{R}}\to{\mathbb{R}}$ by

$S_{c}(x):=(x-c)_{+}\wedge 1.$

For $o\in X$ we define the (pseudo-)norm
$\left\|\cdot\right\|_{o}\colon\mathfrak{D}(G)\to[0,\infty)$ by

$\left\|f\right\|_{o}:=\sqrt{Q(f)+|f(o)|^{2}}.$

We denote the closure of the space of functions of compact support $C_{c}(X)$
with respect to $\left\|\cdot\right\|_{o}$ by $\mathfrak{D}_{0}(G)$. The
following well-known lemma shows that $\left\|\cdot\right\|_{o}$ is indeed a
norm and that the space $\mathfrak{D}_{0}(G)$ does not depend on the choice of
$o\in X$, see e.g. [19, Proposition 1.6]. Its proof relies on the
connectedness of $G$, which we always assume in this text (see above).

######  Lemma 2.3.

Let $G=(X,b)$ be a graph and let $o\in X$.

  1. (a)

$\left\|\cdot\right\|_{o}$ is a norm and
$(\mathfrak{D}(G),\left\|\cdot\right\|_{o})$ is a Banach space.

  2. (b)

$f_{n}\to f$ with respect to $\left\|\cdot\right\|_{o}$ implies $f_{n}\to f$
pointwise.

  3. (c)

For $o^{\prime}\in X$ the norms $\left\|\cdot\right\|_{o}$ and
$\left\|\cdot\right\|_{o^{\prime}}$ are equivalent.

A measure $m$ on $X$ induces the Hilbert space

$\ell^{2}(X,m)=\\{f\in C(X)\mid\sum\limits_{x\in X}m(x)|f(x)|^{2}<\infty\\}$

with inner product

$\langle f,g\rangle_{m}=\sum\limits_{x\in X}m(x)f(x)g(x)$

and corresponding norm $\left\|\cdot\right\|_{m}$. We denote by
$H^{1}(G,m):=\ell^{2}(X,m)\cap\mathfrak{D}(G)$ the corresponding first-order
Sobolev space. Equipped with the inner product

$\langle f,g\rangle_{Q,m}:=\langle f,g\rangle_{m}+Q(f,g)$

it is a Hilbert space. We denote the associated norm by
$\left\|\cdot\right\|_{Q,m}$. For a proof of the completeness of this space we
refer the reader to [19, Section 1.3], where the completeness of $H^{1}(G,m)$
is discussed as closedness of the Dirichlet form $Q^{(N)}$ (in the notation
used there).

###  2.2. Intrinsic metrics

In this section we introduce the (pseudo)metrics relevant for our
considerations and discuss their properties.

A symmetric function $\sigma:X\times X\to[0,\infty)$ is called a
_pseudometric_ if it satisfies the triangle inequality, i.e. if for all
$x,y,z\in X$ it satisfies

$\sigma(x,y)\leq\sigma(x,z)+\sigma(z,y).$

For $r\geq 0$ and $x\in X$ we denote the corresponding ball of radius $r$
around $x$ by

$B_{r}^{\sigma}(x):=\\{y\in X\mid\sigma(x,y)\leq r\\}.$

For $x\in X$ the distance $\sigma_{U}$ from a nonempty subset $U\subseteq X$
is defined by

$\sigma_{U}(x):=\sigma(x,U):=\inf\limits_{y\in U}\sigma(x,y)$

and the _diameter_ of $U$ with respect to $\sigma$ is

$\mathrm{diam}_{\sigma}(U):=\sup\limits_{x,y\in U}\sigma(x,y).$

A function $f$ on $X$ is called Lipschitz-function with respect to the
pseudometric $\sigma$ if there exists a $C>0$ with $|f(x)-f(y)|\leq
C\sigma(x,y)$ for all $x,y\in X$. We then also say that $f$ is a $C$-Lipschitz
function. The set of all Lipschitz-functions with respect to $\sigma$ is
denoted by ${\rm Lip}_{\sigma}(X)$.

For a graph $G=(X,b)$ a pseudometric $\sigma$ is called _intrinsic_ with
respect to the measure $m$ if for all $x\in X$ it satisfies

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

We write $\mathfrak{M}(G)$ for the set of pseudometrics that are intrinsic
with respect to a finite measure. Clearly, a pseudometric $\sigma$ belongs to
$\mathfrak{M}(G)$ if and only if

$\sum_{x,y\in X}b(x,y)\sigma(x,y)^{2}<\infty$

holds.

######  Remark (Background on intrinsic metrics).

Intrinsic metrics have long proven to be a useful tool in spectral geometry of
manifolds and, more generally, for strongly local Dirichlet spaces, see e.g.
Sturm’s seminal work [23, 24]. For general Dirichlet spaces, including graphs,
a systematic approach was developed in [3]. A key point in [3] is a Rademacher
type theorem. In the context of graphs this theorem says that a pseudometric
$\sigma$ is intrinsic if and only if for all $1$-Lipschitz functions $f\colon
X\to{\mathbb{R}}$ with respect to $\sigma$ we have $|\nabla f|^{2}\leq 1$.
Here, for $f\in C(X)$ and $x\in X$ the quantity

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

can be interpreted as the square of the norm of the discrete gradient of $f$
at $x$ (with respect to the measure $m$). For graphs with measure $m$ for
which the scaled degree $\deg/m$ is uniformly bounded the combinatorial metric
is an intrinsic metric (up to a constant). For graphs with unbounded degree
this is not the case anymore. For such graphs, intrinsic metrics (rather than
the combinatorial metric) have turned out to be the right metrics for various
questions, see e.g. the survey [10]. The present article can also be seen as a
point in case.

There are strong ties between functions of finite Dirichlet energy and
intrinsic pseudometrics with respect to a finite measure. These will be of
relevance for some of our theorems below.

######  Lemma 2.4 (From $\mathfrak{M}(G)$ to $\mathfrak{D}(G)$).

Let $G=(X,b)$ be a graph. Let $\sigma$ be an intrinsic pseudometric with
respect to the finite measure $m$. Let $U$ be a subset of $X$. Then, the
following statements hold:

  1. (a)

Any function $f$ that is $C$-Lipschitz with respect to $\sigma$ and constant
on $U$ satisfies

$Q(f)\leq C^{2}\min\\{m(X),2m(X\setminus U)\\}.$

  2. (b)

The inequality

$Q(\sigma_{U})\leq\min\\{m(X),2m(X\setminus U)\\}$

is valid and, in particular, $\sigma_{U}$ belongs to $\mathfrak{D}(G)$.

  3. (c)

The inequality

$Q(f)\leq C^{2}m(X)$

holds for any $C$-Lipschitz function $f$ with respect to $\sigma$. In
particular, any Lipschitz function with respect to $\sigma$ belongs to
$\mathfrak{D}(G)$.

###### Proof.

Clearly, both (b) and (c) are immediate consequences of (a). Thus, we only
show (a). It suffices to consider the case $C=1$ as for general $C>0$ the
function $g=\frac{1}{C}f$ is $1$-Lipschitz with $Q(g)=\frac{1}{C^{2}}Q(f)$.
So, let $f$ be a $1$-Lipschitz function vanishing on $U$. The bound $Q(f)\leq
m(X)$ follows easily from the estimate

$Q(f)=\frac{1}{2}\sum_{x,y}b(x,y)(f(x)-f(y))^{2}\leq\sum_{x\in
X}\left(\frac{1}{2}\sum_{y\in X}b(x,y)\sigma(x,y)^{2}\right)$

and the fact that $\sigma$ is intrinsic with respect to $m$. The other
estimate can be shown as follows: Using

  * •

$f(x)-f(y)=0$ for all $x,y\in U$ and

  * •

$|f(x)-f(y)|\leq\sigma(x,y)$ for all $x,y\in X$

we infer

$\displaystyle Q(f)$ $\displaystyle=\frac{1}{2}\sum_{x,y\in
X}b(x,y)(f(x)-f(y))^{2}$ $\displaystyle=\frac{1}{2}\sum_{(x,y)\in
X^{2}\setminus U^{2}}b(x,y)(f(x)-f(y))^{2}$
$\displaystyle\leq\frac{1}{2}\sum_{(x,y)\in X^{2}\setminus
U^{2}}b(x,y)\sigma(x,y)^{2}$ $\displaystyle=\sum_{y\in X\setminus
U}\left(\frac{1}{2}\sum_{x\in X}b(x,y)\sigma(x,y)^{2}\right)+\sum_{x\in
X\setminus U}\left(\frac{1}{2}\sum_{y\in U}b(x,y)\sigma(x,y)^{2}\right)$
$\displaystyle\leq 2m(X\setminus U).\qed$

######  Remark.

Clearly, the estimates given in the previous lemma trivially continue to hold
if $m$ is not a finite measure.

######  Lemma 2.5 (From to $\mathfrak{D}(G)$ to $\mathfrak{M}(G)$).

Let $G=(X,b)$ be a graph. Then, for any function $f$ of finite energy the
function

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

is an intrinsic pseudometric with respect to the finite measure $m_{f}$ that
is given by

$m_{f}(x)=\frac{1}{2}\sum\limits_{y\in X}b(x,y)\sigma_{f}(x,y)^{2}.$

The function $f$ is $1$-Lipschitz with respect to $\sigma_{f}$ and
$m_{f}(X)=Q(f)$.

###### Proof.

This is already shown in [6, Proposition 3.11]. ∎

By the preceding lemma any $f$ of finite energy comes with a pseudometric
$\sigma_{f}$ that is intrinsic with respect to a finite measure. In general,
this $\sigma_{f}$ will not be a metric (as values of $f$ in different points
need not be distinct). However, this can easily be achieved by an arbitrarily
small perturbation as the next proposition shows.

######  Proposition 2.6 (Small perturbation).

Let $G=(X,b)$ be a graph.

  1. (a)

For any $\varepsilon>0$ there exist $s_{x}>0$, $x\in X$, such that any
function $g\colon X\to\mathbb{R}$ with $g(x)\in(-s_{x},s_{x})$ for all $x\in
X$ satisfies $Q(g)<\varepsilon.$

  2. (b)

For any $f\in\mathfrak{D}(G)$ and any $\varepsilon>0$ there exists a function
$f_{\varepsilon}\in\mathfrak{D}(G)$ with $f_{\varepsilon}(x)\neq
f_{\varepsilon}(y)$ for all $x,y\in X$ with $x\neq y$ and

$\sup_{x\in X}|f(x)-f_{\varepsilon}(x)|<\varepsilon\mbox{ and
}|Q(f-f_{\varepsilon})|<\varepsilon.$

###### Proof.

(a): We write $1_{x}$ for the characteristic function of $x\in X$. Then
$Q(1_{x})=\deg(x)<\infty$. For $x\in X$ we choose $s_{x}>0$ with

$\sum_{x\in X}s_{x}Q(1_{x})^{1/2}<\sqrt{\varepsilon}.$

Choose a sequence $(F_{n})$ of finite subsets of $X$ with $F_{n}\subseteq
F_{n+1}$ and $X=\bigcup_{n}F_{n}$. Then, any $g\colon X\to\mathbb{R}$ with
$g(x)\in(-s_{x},s_{x})$ is the pointwise limit of the functions
$g_{n}:=\sum_{x\in F_{n}}g(x)1_{x}$. The pointwise lower semicontinuity of $Q$
together with Cauchy-Schwarz inequality yield

$\displaystyle Q(g)\leq\liminf_{n\to\infty}Q(g_{n})$
$\displaystyle\leq\liminf_{n\to\infty}\sum_{x,y\in
F_{n}}|g(x)||g(y)|Q(1_{x})^{1/2}Q(1_{y})^{1/2}$
$\displaystyle\leq\left(\sum_{x\in
X}s_{x}Q(1_{x})^{1/2}\right)^{2}<\varepsilon.$

(b): This follows from (a). Let $\varepsilon>0$ be given and chose $s_{x}$,
$x\in X$, according to (a). Without loss of generality we can assume
$s_{x}<\frac{\varepsilon}{2}$. Now let real numbers $u_{x}$, $x\in X$, be
given such that $u_{x}-u_{y}$ is irrational for any $x\neq y$. Then, for any
$x\in X$ we can choose an $t_{x}\in(-s_{x},s_{x})$ such that
$f(x)-u_{x}-t_{x}$ is rational. Then, $f_{\varepsilon}$ with

$f_{\varepsilon}(x)=f(x)-t_{x}$

for all $x\in X$ satisfies
$\sup_{x}|f(x)-f_{\varepsilon}(x)|\leq\sup_{x}s_{x}<\varepsilon$ as well as
$Q(f-f_{\varepsilon})<\varepsilon$. Moreover, the values of $f_{\varepsilon}$
are pairwise different as for $x\neq y$ we have

$(f(x)-t_{x})-(f(y)-t_{y})=(u_{x}-u_{y})+(f(x)-u_{x}-t_{x})-(f(y)-u_{y}-t_{y})$

can not vanish (as it is the sum of an irrational number and a rational
number.) ∎

For us a special class of pseudometrics will be particularly useful. They will
be introduced next. Given a symmetric function $w\colon X\times
X\to[0,\infty)$ and a (possibly infinite) path $\gamma=(x_{1},x_{2},\ldots)$
in $G$ we define the length of $\gamma$ with respect to $w$ by

$L_{w}(\gamma):=\sum_{i}w(x_{i},x_{i+1})\in[0,\infty].$

Since we always assume connectedness, this induces the _path pseudometric_
$d_{w}$ on $X$ via

$d_{w}(x,y)=\inf\\{L_{w}(\gamma)\mid\gamma\text{ a path from $x$ to $y$}\\}.$

We say that $\sigma$ is a path pseudometric on $X$ if $\sigma=d_{w}$ for some
symmetric function $w$. A symmetric function $w\colon X\times X\to[0,\infty)$
is called _edge weight_ if $w(x,y)>0$ for all $(x,y)\in E$.

A symmetric function $w$ is called _adapted_ with respect to the graph
$G=(X,b)$ and the measure $m$ if for all $x\in X$ it satisfies

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

The following lemma summarizes some elementary properties of path
pseudometrics.

######  Lemma 2.7 (Path pseudometrics).

Let $G=(X,b)$ be a graph and let $w\colon X\times X\to[0,\infty)$ be a
symmetric function. Then $d_{w}$ is a pseudometric that satisfies
$d_{w}(x,y)\leq w(x,y)$ if $x\sim y$. Moreover, the following are satisfied.

  1. (a)

If $w$ is a pseudometric, then $d_{w}\geq w$. In particular,
$d_{w}(x,y)=w(x,y)$ for all $x,y\in X$ with $x\sim y$.

  2. (b)

If $w$ is adapted with respect to the measure $m$, then $d_{w}$ is intrinsic
with respect to the measure $m$.

  3. (c)

For $\sigma=d_{w}$ the equality $d_{\sigma}=\sigma$ holds.

###### Proof.

The trivial path $(x,y)$ is one of the paths over which the infimum in the
definition of $d_{w}$ is taken. As $L_{w}((x,y))=w(x,y)$, the inequality
$d_{w}(x,y)\leq w(x,y)$ is immediate.

(a): Given a path $\gamma=(x=x_{1},\ldots,x_{n}=y)$, an iteration of the
triangle inequality $w(x_{1},x_{k+1})\leq w(x_{1},x_{k})+w(x_{k},x_{k+1})$
yields

$w(x,y)\leq\sum\limits_{i=1}^{n-1}w(x_{i},x_{i+1})=L_{w}(\gamma).$

(b): This is an immediate consequence of the inequality $d_{w}(x,y)\leq
w(x,y)$ for all $x,y\in X$ with $x\sim y$.

(c): As $\sigma=d_{w}$ is a pseudometric, (a) gives $\sigma\leq d_{\sigma}$
and, for $x,y\in X$ with $x\sim y$, even $\sigma(x,y)=d_{\sigma}(x,y)$. For
arbitrary $x,y\in X$ let a path $\gamma=(x=x_{1},\ldots,x_{n}=y)$ be given.
Then a short computation involving what we have shown already and the triangle
inequality gives

$L_{w}(\gamma)=\sum_{j=1}^{n-1}w(x_{j},x_{j+1})\geq\sum_{j=1}^{n-1}\sigma(x_{j},x_{j+1})=\sum_{j=1}^{n}d_{\sigma}(x_{j},x_{j+1})\geq
d_{\sigma}(x,y).$

Taking the infimum over all $\gamma$ we find $\sigma(x,y)\geq
d_{\sigma}(x,y)$. ∎

We note the following consequence of our considerations: If $f$ is a function
of finite energy on the graph $(X,b)$, then $\sigma_{f}$ (defined in Lemma
2.5) is an intrinsic pseudometric with respect to $m_{f}$. Now, we can also
consider $\sigma_{f}$ as a symmetric function (adapted to $m_{f}$). This
induces the path pseudometric $d_{f}:=d_{\sigma_{f}}$. The preceding lemma
immediately gives the following.

######  Corollary 2.8.

Let $G=(X,b)$ be a graph and let $f\in\mathfrak{D}(G)$. Then,
$d_{f}=d_{\sigma_{f}}$ is an intrinsic metric with respect to $m_{f}$ and

$d_{f}(x,y)=|f(x)-f(y)|$

holds for all $x,y\in X$ with $b(x,y)>0$.

###### Proof.

By the preceding lemma we have $d_{f}=d_{\sigma_{f}}\leq\sigma_{f}$ as well as
$d_{f}(x,y)=\sigma_{f}(x,y)=|f(x)-f(y)|$ for all $x,y\in X$ with $b(x,y)>0$. ∎

######  Remark.

Let a graph $G=(X,b)$ be given. Define $\widetilde{Q}$ on the set of symmetric
functions $w\colon X\times X\to[0,\infty)$ by

$\widetilde{Q}(w):=\frac{1}{2}\sum_{x,y}b(x,y)w(x,y)^{2}\in[0,\infty].$

Then, part of our considerations can be understood in terms of
$\widetilde{Q}$. As this may be instructive we give a brief discussion in the
present remark: For a symmetric $w\colon X\times X\to[0,\infty)$ we define

$m_{w}\colon X\to[0,\infty],\quad m_{w}(x)=\frac{1}{2}\sum_{y\in
X}b(x,y)w(x,y)^{2}$

and $m_{w}(X):=\sum_{x\in X}m_{w}(x)$. Finally, for $f\colon X\to\mathbb{R}$
define the symmetric function $\sigma_{f}\colon X\times X\to[0,\infty)$ with
$\sigma_{f}(x,y):=|f(x)-f(y)|$. Then, the following holds:

  1. (a)

Let $w$ be a symmetric weight. Then, $\widetilde{Q}(w)=m_{w}(X)$, where the
value $\infty$ is allowed. If $w$ is actually a pseudometric, then
$\widetilde{Q}(d_{w})=\widetilde{Q}(w)$ holds.

  2. (b)

Let $\sigma$ be a pseudometric on $X$. Then, $m_{\sigma}$ is a finite measure
if and only if $\sigma$ belongs to $\mathfrak{M}(G)$. If $m_{\sigma}$ is a
finite measure it is the smallest measure with respect to which $\sigma$ is an
intrinsic metric.

  3. (c)

For $f\colon X\to\mathbb{R}$ the equality $Q(f)=\widetilde{Q}(\sigma_{f})$
holds, where the value $\infty$ is allowed. Moreover, $f$ belongs to
$\mathfrak{D}(G)$ if and only if $\sigma_{f}$ belongs to $\mathfrak{M}(G)$.

  4. (d)

The function $f\colon X\to\mathbb{R}$ is $1$-Lipschitz with respect to the
pseudometric $\sigma$ if and only if $\sigma_{f}\leq\sigma$ holds. In this
case, $Q(f)\leq\widetilde{Q}(\sigma_{f})$ is valid.

As mentioned already we think of the space $X$ underlying the graph $(X,b)$ as
equipped with discrete topology. Thus, metrics compatible with the discrete
topology are of particular relevance for us. The following lemma ensures the
existence of such metrics in $\mathfrak{M}(G)$.

######  Lemma 2.9.

Let $G=(X,b)$ be a graph. Then, there exists a metric in $\mathfrak{M}(G)$
that induces the discrete topology.

###### Proof.

Let ${\mathbb{N}}\to X,n\mapsto x_{n},$ be an enumeration of $X$. We define

$f\colon X\rightarrow(0,\infty),\quad
f(x_{n})=\frac{1}{\sqrt{2^{n}{\mathrm{deg}}(x_{n})}},$

and

$\sigma\colon X\times
X\to[0,\infty),\quad\sigma(x,y)=\begin{cases}\max\\{f(x),f(y)\\}&\text{for
}x\neq y\\\ 0&\text{else}\end{cases}.$

It is readily verified that $\sigma$ is a metric (and even an ultrametric). By
$\sigma(x,y)^{2}\leq f(x)^{2}+f(y)^{2}$, the symmetry of $b$ and Fubini’s
theorem we find

$\displaystyle\sum\limits_{x\in X}b(x,y)\sigma(x,y)^{2}$ $\displaystyle\leq$
$\displaystyle\sum\limits_{x,y\in X}b(x,y)(f(x)^{2}+f(y)^{2})$
$\displaystyle=$ $\displaystyle 2\sum\limits_{x,y\in X}b(x,y)f(x)^{2}$
$\displaystyle=$ $\displaystyle 2\sum_{x\in X}{\mathrm{deg}}(x)f(x)^{2}.$

Now, the definition of $f$ gives

$2\sum_{x\in X}{\mathrm{deg}}(x)f(x)^{2}\leq 2$

and it follows that $\sigma$ is an intrinsic metric with respect to a finite
measure.

The metric $\sigma$ induces the discrete topology as the distance from any
point to $x\in X$ is bounded from below by $f(x)>0$. ∎

###  2.3. Boundaries of graphs

As outlined in the introduction completions and boundaries of graphs will be
most relevant for our considerations. Here we introduce the corresponding
notions.

Let $X$ be a countable set. Let $\sigma$ be a pseudometric on $X$. The
completion of $X$ with respect to $\sigma$ is defined as the set of
equivalence classes of $\sigma$-Cauchy sequences in $X$, where two such
sequences $(a_{n})$ and $(b_{n})$ are considered to be equivalent if

$\lim_{n\rightarrow\infty}\sigma(a_{n},b_{n})=0.$

This set is denoted by $\overline{X}^{\sigma}$ and contains a quotient of the
vertex set $X$ as the classes of the constant sequences. learly, $\sigma$ can
be extended to a pseudometric on $X$ and this extension will - by a slight
abuse of notation - also denoted by $\sigma$. Subsequently, the boundary is
defined as

$\partial_{\sigma}X=\overline{X}^{\sigma}\setminus(X/\simeq),$

where $x\simeq y$ if $\sigma(x,y)=0$. A graph is called _metrically complete_
with respect to a pseudometric if the boundary is empty. Clearly, if $\sigma$
is a metric then $\overline{X}^{\sigma}$ contains a copy of $X$, this copy is
dense, and and our definition of metric completeness agrees with the usual
definition (that any Cauchy-sequence converges).

There are further notions of completeness relevant to us. Let $G=(X,b)$ be a
graph and let $w$ be an edge weight. The pseudometric space $(X,d_{w})$ is
called _geodesically complete_ if every infinite path has infinite length with
respect to $w$. For later purposes we recall the following discrete Hopf-Rinow
type theorem that characterizes geodesic completeness, see [8, Theorem A.1]
and, for further generalizations, see also [13].

######  Theorem 2.10 (Hopf-Rinow type theorem).

Let $G=(X,b)$ be a locally finite graph and let $w$ be an edge weight. Then
$d_{w}$ is a metric that induces the discrete topology on $X$. Moreover, the
following assertions are equivalent:

  1. (i)

$(X,d_{w})$ is a complete metric space.

  2. (ii)

$(X,d_{w})$ is geodesically complete.

  3. (iii)

Every distance ball is finite.

  4. (iv)

Every bounded and closed set is compact.

Boundaries of graphs can not only arise from metric completions but also from
compactifications. In fact, they can arise whenever the set $X$ underlying the
graph is suitable extended. We finish this section with a short discussion of
this aspect. Let $X$ be a countable set. Let $Y$ be a topological Hausdorff
space. We say that $X$ embeds densely  in the topological space $Y$ if $Y$
contains a copy of $X$, the restriction of the topology of $Y$ on $X$ is the
discrete topology, and $X$ is dense in $Y$. Clearly, $Y$ must be separable
whenever $X$ embeds densely in it. Whenever $X$ embeds densely in $Y$ we
define the boundary $\partial_{Y}X$ of $X$ in $Y$ by

$\partial_{Y}X:=Y\setminus X.$

The complement (in $Y$) of any finite subset of $X$ is open in $Y$ (as any
finite set is compact and then must be closed due to Hausdorffness). Hence,
any such a complement is an open neighborhood of $\partial_{Y}X$. In
particular, any function $h$ with finite support on $X$ can be extended (by
zero) to a continuous function on $Y$.

Clearly, $X$ embeds densely in $\overline{X}^{\sigma}$ whenever $\sigma$ is a
metric on $X$ inducing the discrete topology. This is what we have discussed
above. Then,

$\partial_{\sigma}X=\partial_{\overline{X}^{\sigma}}X$

holds.

If $X$ embeds densely in a compact $Y$, then $Y$ is called a compactification
of $X$. In this case the open neighborhoods of $\partial X$ are exactly given
by the complements of finite sets of $X$ (as the complement of any open
neighborhood of $\partial_{Y}X$ must be a closed, and hence, compact subset of
$X$). A particular instance is given by the one-point-compactification. It is
given by the set $Y=X\cup\\{\mbox{pt}\\}$, where pt is an arbitrary additional
point, and this set is equipped with topology given by the family of all
subsets of $Y$ that are either subsets of $X$ or whose complement is finite.
In this case the boundary of $\partial_{Y}X$ is just pt.

##  3\. Capacity of sets in the boundary and infinite paths

In this section we introduce the capacity and study the capacity of sets in
the boundary with respect to an intrinsic metric.

Let $G=(X,b)$ be a graph and let $m\colon X\to(0,\infty)$ be a measure. The
_capacity_ of a subset $U\subseteq X$ is defined by

${\rm cap}_{m}(U):=\inf\\{\left\|f\right\|_{Q,m}^{2}\mid f\in H^{1}(G,m)\text{
with }f\geq 1\text{ on }U\\},$

with the convention that ${\rm cap}_{m}(U)=\infty$ if the set in the above
definition is empty. Using the fundamental contraction property, we can assume
$0\leq f\leq 1$ in this definition, since $(f\wedge 1)_{+}$ satisfies the same
constraints as $f$ but reduces the $\left\|\cdot\right\|_{Q,m}$-norm compared
to $f$.

Whenever $X$ embeds densely in $Y$ we can extend the capacity to subsets of
$Y$ by setting

${\rm cap}_{m}(A):=\inf\\{{\rm cap}_{m}(O\cap X)\mid O\text{ open in }Y\text{
with }A\subseteq O\\}.$

Since by assumption every subset $A\subseteq X$ is open in $Y$ (as the
topology of $Y$ induces the discrete topology on $X$) both definitions of
capacity on $X$ are compatible. This definition can in particular be applied
to the completion $\overline{X}^{\sigma}$, whenever the metric $\sigma$
induces the discrete topology on $X$.

The capacity is an outer measure on the power set of $Y$ with $m(A)\leq{\rm
cap}_{m}(A)$ for all $A\subseteq X$ and ${\rm cap}_{m}(Y)\leq m(X)$, see e.g.
[4, Theorem 2.1.1 and Theorem A.1.2].

Next we discuss how the vanishing of the capacity of subsets of the boundary
can be characterized with limits of functions of finite energy.

######  Definition 3.1 (Limes inferior).

Let $X$ be a countable set, let $\sigma$ be a metric on $X$ that induces the
discrete topology and let $f\colon X\rightarrow\mathbb{R}$. For
$A\subseteq\overline{X}^{\sigma}$ the _limes inferior of $f$ at $A$ with
respect to $\sigma$_ is defined by

$\liminf\limits_{x\rightarrow A}f(x):=\sup\\{\inf\\{f(x)\mid x\in U\cap
X\\}\mid U\ \mathrm{open}\ \mathrm{in}\ \overline{X}^{\sigma}\text{ with
}A\subseteq U\\}.$

Moreover, we define the limes inferior at infinity by

$\liminf\limits_{x\rightarrow\infty}f(x):=\sup\\{\inf\\{f(x)\mid x\in
X\setminus F\\}\mid F\subseteq X\ \mathrm{finite}\\}.$

######  Remark.

For us the case where $\liminf$ equals $\infty$ and the case of compact
$\overline{X}^{\sigma}$ is is particularly relevant. In this context we note
the following.

  1. (a)

We have $\liminf_{x\rightarrow A}f(x)=\infty$ if and only if
$\lim_{n\to\infty}f(x_{n})=\infty$ for each sequence $(x_{n})$ in $X$ with
$\sigma(x_{n},A)\to 0$, $n\to\infty$.

  2. (b)

We have $\liminf_{x\to\infty}f(x)=\infty$ if and only if
$\lim_{n\to\infty}f(x_{n})=\infty$ for any sequence $(x_{n})$ converging to pt
in the one-point-compactification of $X$. In fact, this easily shows that
$\liminf_{x\to\infty}f(x)=\infty$ if and only if
$\lim_{n\to\infty}f(x_{n})=\infty$ for any sequence $(x_{n})$ converging to
some $y\in\partial_{Y}X$, where $Y$ is a compactification of $X$.

  3. (c)

If $\sigma$ induces the discrete topology on $X$ and $(X,\sigma)$ is pre-
compact, then every every open neighborhood $U$ of $\partial_{\sigma}X$ in
$\overline{X}^{\sigma}$ has the form $U=X\setminus F$ for some finite
$F\subseteq X$. Hence, in this case

$\liminf_{x\rightarrow\infty}f(x)=\liminf_{x\rightarrow\partial_{\sigma}X}f(x).$

In this sense, the limes inferior at infinity is the limes inferior at the
boundary for metric compactifications of $X$.

It turns out that $\liminf_{x\to\infty}$ governs
$\liminf_{x\to\partial_{\sigma}X}$ in the following sense.

######  Proposition 3.2.

Let $X$ be a countable set. Let $f:X\to\mathbb{R}$ be given. Then,

$\liminf_{x\to\partial_{\sigma}X}f(x)\geq\liminf_{x\to\infty}f(x)$

for any metric $\sigma$ on $X$ that induces the discrete topology.

###### Proof.

Any finite set $F$ in $X$ is compact in $\overline{X}^{\sigma}$ and, hence,
closed. Thus, for any finite set $F$ in $X$ the set
$\overline{X}^{\sigma}\setminus F$ is an open neighborhood of
$\partial_{\sigma}X$. We obtain

$\displaystyle\liminf\limits_{x\rightarrow\partial_{\sigma}X}f(x)$
$\displaystyle=\sup\\{\inf\\{f(x)\mid x\in U\cap X\\}\mid U\text{ open with
}\partial_{\sigma}X\subseteq U\\}$ $\displaystyle\geq\sup\\{\inf\\{f(x)\mid
x\in X\setminus F\cap X\\}\mid F\subseteq X\text{ finite}\\}$
$\displaystyle\geq\liminf_{x\to\infty}f(x).\qed$

With the help of the limes inferior we can characterize sets of capacity zero
in the boundary.

######  Lemma 3.3 (Characterization of zero capacity sets in the boundary).

Let $G=(X,b)$ be an infinite graph and $\sigma$ be a metric on $G$ that
induces the discrete topology. Further, let $A\subseteq\partial_{\sigma}X$.
The following assertions are equivalent:

  1. (i)

For one finite measure $m$ on $X$ we have ${\rm cap}_{m}(A)=0$.

  2. (ii)

For all finite measures $m$ on $X$ we have ${\rm cap}_{m}(A)=0$.

  3. (iii)

There exists $f\in\mathfrak{D}(G)$ with $\liminf\limits_{x\rightarrow
A}f(x)=\infty.$

###### Proof.

(i) $\Rightarrow$ (iii): The statement ${\rm cap}_{m}(A)=0$ implies the
existence of sequences of open sets $U_{n}\supseteq A$ and functions
$f_{n}\geq 1_{U_{n}}$ that satisfy

$\lim\limits_{n\rightarrow\infty}\left\|f_{n}\right\|_{Q,m}=\lim\limits_{n\rightarrow\infty}\sqrt{Q(f_{n})+\left\|f_{n}\right\|^{2}_{m}}=0.$

By restricting to a subsequence we can assume without loss of generality that

$\sum\limits_{n\in\mathbb{N}}\left\|f_{n}\right\|_{Q,m}<\infty.$

This implies that the sum $f:=\sum_{n\in\mathbb{N}}f_{n}$ converges in the
Hilbert space $H^{1}(G,m)$. In particular, $f\in\mathfrak{D}(G)$. By the
choice of the $f_{n}$ we have $f\geq N$ on the set $\bigcap_{n=1}^{N}U_{n},$
which is an open set that contains $A$. This proves that
$\liminf_{x\rightarrow A}f(x)$ is at least $N$. Since this is true for all
$N\in\mathbb{N}$, the supremum has to be infinite.

(iii) $\Rightarrow$ (ii): Let $f\in\mathfrak{D}(G)$ satisfy (iii). Without
loss of generality we assume $f\geq 0$, for otherwise we can replace $f$ by
$|f|$, which also has finite energy due to Theorem 2.2. We slice $f$ into the
parts

$f_{n}:=(f-n)_{+}\wedge 1.$

First, we observe that $0\leq f_{n}\leq 1$ and $f=\sum_{n=0}^{\infty}f_{n}$
pointwise. Moreover, Theorem 2.2 yields $f_{n}\in\mathfrak{D}(G)$ and since
$m$ is finite and the $f_{n}$ are bounded, we have $f_{n}\in H^{1}(G,m)$.
Because $\liminf_{x\rightarrow A}f(x)=\infty$, for every $n\in\mathbb{N}_{0}$
there is an open set $U_{n}\supseteq A$ such that $f\geq n$ on $U_{n}\cap X$.
By construction, for $x\in X$ the inequality $f(x)\geq n+1$ implies
$f_{n}(x)=1$. Combining these observations we conclude $f_{n}\geq 1_{X\cap
U_{n+1}}.$

Altogether, this shows that the functions $f_{n}$ are usable in the definition
of the capacity of $A$ and

${\rm cap}_{m}(A)\leq\left\|f_{n}\right\|_{Q,m}.$

We prove $\left\|f_{n}\right\|_{Q,m}\to 0$, as $n\to\infty.$

It is readily verified that for $n\neq m$ and $x,y\in X$ the product
$(f_{m}(x)-f_{m}(y))(f_{n}(x)-f_{n}(y))$ is always nonnegative, so that

$Q(f_{n},f_{m})=\frac{1}{2}\sum_{x,y\in
X}b(x,y)(f_{m}(x)-f_{m}(y))(f_{n}(x)-f_{n}(y))\geq 0.$

Recall that for $N\in{\mathbb{N}}$ we defined $C_{[0,N]}f=f_{+}\wedge N$.
Using Proposition 2.2, the definition of $f_{n}$ and the previous observation,
we obtain

$\displaystyle\sum\limits_{n=0}^{N-1}Q(f_{n})$
$\displaystyle\leq\sum\limits_{n=0}^{N-1}Q(f_{n})+\sum\limits_{\begin{subarray}{c}0\leq
m,n\leq N-1\\\ m\neq n\end{subarray}}Q(f_{m},f_{n})$
$\displaystyle=Q\left(\sum\limits_{n=0}^{N-1}f_{n}\right)=Q(C_{[0,N]}f)\leq
Q(f).$

Since $N$ was arbitrary and $Q(f)<\infty$, we arrive at
$\lim_{n\rightarrow\infty}Q(f_{n})=0$. The convergence
$\lim_{n\rightarrow\infty}\left\|f_{n}\right\|_{m}=0$ follows from Lebesgue’s
dominated convergence theorem. This leads to
$\lim_{n\rightarrow\infty}\left\|f_{n}\right\|_{Q,m}=0$ and thus, ${\rm
cap}_{m}(A)=0.$

(ii) $\Rightarrow$ (i): This is clear. ∎

######  Remark.

  1. (a)

The lemma shows that having capacity zero does not depend on the choice of the
finite measure. Indeed, we do not even need to assume that $m$ is strictly
positive. If we only assume that $m(o)>0$ for one $o\in X$, the space
$H^{1}(X,m)$ continuously embeds into
$(\mathfrak{D}(G),\left\|\cdot\right\|_{o})$ and the proof can be carried out
in the space $(\mathfrak{D}(G),\left\|\cdot\right\|_{o})$. The advantage of
working in $H^{1}(G,m)$ is that it is related to intrinsic metrics with
respect to $m$.

  2. (b)

The inequality used in the proof of the implication (iii) $\Rightarrow$ (ii)
can be extended to a more general form. Let $f:X\rightarrow\mathbb{R}$ be a
function of finite energy and let
$C_{1},C_{2}:\mathbb{R}\rightarrow\mathbb{R}$ be two monotone increasing
$1$-Lipschitz functions. Then

$Q(C_{1}\circ f+C_{2}\circ f)\geq Q(C_{1}\circ f)+Q(C_{2}\circ f).$

In the above proof this observation is applied to the monotone increasing
contractions $S_{n},n\in\mathbb{N}_{0}$, with $S_{n}(x)=(x-n)_{+}\wedge 1.$

One can understand the preceding result also as saying that the sets
$A\subseteq\partial_{\sigma}X$ with zero capacity are infinitely far away from
any finite set. More specifically, the following holds.

######  Corollary 3.4 (Capacity zero sets in the boundary have infinite
distance).

Let $G=(X,b)$ be an infinite graph and $\sigma$ a metric on $G$ that induces
the discrete topology. Further, let $A\subseteq\partial_{\sigma}X$. Then,
$\partial_{\sigma}A$ has zero capacity (with respect to any finite measure) if
and only if there exists an intrinsic metric $\varrho\in\mathfrak{M}(G)$ such
that for any finite $F$ in $X$ and any $r>0$ there exists an open neighborhood
$U$ of $A$ with

$\varrho(U\cap X,F):=\inf\\{\varrho(z,x)\mid z\in U\cap X,x\in F\\}\geq r.$

###### Proof.

Assume that $A$ has capacity zero (with respect to any finite measure). By the
previous lemma, there exists an $f\in\mathfrak{D}(G)$ with $\liminf_{x\to
A}f(x)=\infty$. Without loss of generality we can assume $f(x)\neq f(y)$ for
all $x,y\in X$ with $x\neq y$ (else we could add an arbitrary small
perturbation by Proposition 2.6). Then, $\varrho:=\sigma_{f}$ is an intrinsic
metric with respect to a finite measure. By $\liminf_{x\to A}f(x)=\infty$ the
metric $\varrho$ has the given property.

Assume now that there exists an intrinsic metric $\varrho$ with respect to the
finite measure $m$ that has the given property. Let an arbitrary finite set
$F$ be given. Then, there exists an open neighborhood $U$ of $A$ with
$\varrho(U\cap X,F)\geq 1$. Hence, $g_{F}:=\varrho_{F}\wedge 1$ satisfies
$0\leq g_{F}\leq 1$, equals $0$ on $F$ and equals $1$ on $U$. Hence,

${\rm cap}_{m}(A)\leq Q(g_{F})+\left|g_{F}\right|_{m}^{2}\leq
Q(\varrho_{F})+m(X\setminus F)\leq 3m(X\setminus F)$

holds, where we used Lemma 2.4 in the last step. As this holds for arbitrary
$F$ we infer ${\rm cap}_{m}(A)=0$. By the previous lemma this implies that the
capacity of $A$ vanishes with respect to any finite measure. ∎

######  Remark.

Replacing $\varrho$ by $d_{\varrho}\leq\varrho$ we can even take the intrinsic
metric in the preceding corollary to be a path metric.

######  Remark.

Lemma 3.3 and its corollary deal with metric completions of $X$. However, they
can directly be extended to any topological Hausdorff space $Y$ in which $X$
embeds densely. Indeed, both the definition of $\liminf_{x\to A}$ and the
proofs of the lemma and its corollary carry verbatim over to this more general
situation. This means in particular that these considerations also holds for
compactifications of $X$.

Next we discuss how the capacity of sets in the metric boundary is related to
infinite paths. We recall the following standard notion for sets of infinite
paths in a graph.

######  Definition 3.5 (Null set of paths).

A set of infinite paths $\Gamma$ in $G=(X,b)$ is called null if there exists
an edge weight $w$ with

$\sum_{x,y\in X}b(x,y)w(x,y)^{2}<\infty$

such that $L_{w}(\gamma)=\infty$ for all $\gamma\in\Gamma$.

Let $\sigma$ be a metric on $X$ that induces the discrete topology. For
$A\subseteq\partial_{\sigma}X$ we denote by $\Gamma_{A,\sigma}$ the set of
infinite paths which have at least one accumulation point with respect to
$\sigma$ lying in $A$.

With the help of our characterization of sets of capacity zero in the boundary
we obtain the following relation between sets of capacity zero in the boundary
and sets of paths with accumulation point in this set.

This is the key observation relating our approach to the classical approach to
recurrence by means of null sets of paths. As noted in the introduction, this
observation was our motivation to write this paper.

######  Theorem 3.6 (Capacity and null sets of paths).

Let $G=(X,b)$ be an infinite graph and let $\sigma$ be an intrinsic metric
with respect to a finite measure $m$ that induces the discrete topology. Let
$A\subseteq\partial_{\sigma}X$ with ${\rm cap}_{m}(A)=0$. Then
$\Gamma_{A,\sigma}$ is null.

###### Proof.

According to the previous lemma there is $f\in\mathfrak{D}(G)$ such that
$\liminf_{x\to A}f(x)=\infty.$ We consider the function $w\colon X\times
X\to{\mathbb{R}}$, $w(x,y)=|f(x)-f(y)|$. Without loss of generality we can
assume $w(x,y)>0$ whenever $(x,y)$ is an edge (else at each vertex $x$ add a
small quantity to $f(x)$ if necessary, see Proposition 2.6). Then

$\sum_{x,y\in X}b(x,y)w(x,y)^{2}\leq 2Q(f)<\infty.$

Let $\gamma=(x_{1},x_{2},\ldots)$ be an infinite path with an accumulation
point in $A$. We obtain

$|f(x_{n})-f(x_{1})|\leq\sum_{k=1}^{n-1}|f(x_{k})-f(x_{k+1})|\leq
L_{w}(\gamma).$

Since $\liminf_{x\to A}f(x)=\infty,$ the left hand side of this inequality
diverges along a suitable subsequence and so we obtain $L_{w}(\gamma)=\infty$.
Hence, $\Gamma_{A,\sigma}$ is null. ∎

The converse seems not to hold due to the complicated behavior of paths at
metric boundaries of general graphs. For trees however we have the following
converse for path metrics. Recall that $(X,b)$ is a tree if it does not have
non-trivial cycles (injective paths $(x_{1},\ldots,x_{n})$ with $x_{1}\sim
x_{n}$).

######  Proposition 3.7.

Let $G=(X,b)$ be a tree and let $\sigma$ be a path metric that induces the
discrete topology on $X$ and is intrinsic with respect to a finite measure
$m$. If for $A\subseteq\partial_{\sigma}X$ the set of paths
$\Gamma_{A,\sigma}$ is null, then ${\rm cap}_{m}(A)=0$.

###### Proof.

Let $w$ be an edge weight for $\Gamma_{A,\sigma}$ as in the definition of null
sets of paths. Fix $o\in X$ and for $x\in X$ let $\gamma_{x}$ be the unique
shortest path with respect to the combinatorial distance connecting $o$ and
$x$ (uniqueness follows from $(X,b)$ being a tree). We define

$f\colon X\to{\mathbb{R}},\quad f(x)=L_{w}(\gamma_{x}).$

Since $(X,b)$ is a tree, for neighbors $x,y\in X$ we have $|f(x)-f(y)|=w(x,y)$
showing $f\in\mathfrak{D}(G)$.

Let $(x_{n})$ be a sequence in $X$ with limit in $x\in A$. We construct a
monotone path $\gamma=(y_{1},y_{2},\ldots)$ (i.e. the combinatorial distance
of $y_{1}$ and $y_{n+1}$ is larger or equal than the combinatrial distance of
$y_{1}$ and $y_{n}$) starting in $o$ such that $y_{n}\to x$ and

$f(x_{k})=f(y_{n_{k}})+d_{w}(x_{k},y_{n_{k}})\geq f(y_{n_{k}})$

for a suitable subsequence $(y_{n_{k}})$. The monotonicity of $\gamma$ and
that $(X,b)$ is a tree imply

$\liminf_{k\to\infty}f(x_{k})\geq\liminf_{k\to\infty}f(y_{n_{k}})=L_{w}(\gamma)=\infty.$

Construction of $\gamma$: We consider $o$ as a root for the graph and denote
by $|x|$ the combinatorial distance of $x$ to $o$. We say that $y$ is an
ancestor of $c$ if all paths from $x$ to $o$ pass through $y$. Since $(X,b)$
is a tree, every $A\subseteq X$ has a unique greatest common ancestor, i.e.,
there exists and element $y\in X$ with:

  * •

$y$ is an ancestor of every element of $A$.

  * •

For every $x\in X$ with $|x|>|y|$ there exists an $a\in A$ such that $x$ is
not an ancestor of $a$.

We let $z_{n}$ be the greatest common ancestor of
$\\{x_{n},x_{n+1},\ldots\\}$. This sequence is monotone as $z_{n}$ is an
ancestor of $\\{x_{n+1},x_{n+2},\ldots\\}$ and hence an ancestor of $z_{n+1}$.
For every $n\in{\mathbb{N}}$ there exists $N>n$ such that the greatest common
ancestor of $\\{x_{n},x_{N}\\}$ is $z_{n}$ (otherwise $z_{n}$ would not be a
greatest common ancestor). Every path from $x_{n}$ to $x_{N}$ passes through
$z_{n}$. Since $\sigma$ is a path metric, this implies

$\sigma(x_{n},x_{N})=\sigma(x_{n},z_{n})+\sigma(z_{n},x_{N})$

and we obtain

$\sigma(x_{n},z_{n})\leq\sup\\{\sigma(x_{n},x_{N})\mid N>n\\}.$

Hence, $(z_{n})$ also converges to $x$ but it need not be a path. We make it a
path by inserting monotone paths from $z_{n}$ to $z_{n+1}$ (these exist since
$y_{n}$ is an ancestor of $y_{n+1}$). Using that $\sigma$ is a path metric
yields that any such additional point $z$ lying between $z_{n}$ and $z_{n+1}$
satisfies

$\sigma(z_{n},z_{m})=\sigma(z_{n},z)+\sigma(z,z_{m})\geq\sigma(z_{n},z).$

Hence, also the so-constructed monotone path $(y_{n})$ converges to $x$. We
choose $n_{k}$ such that $y_{n_{k}}=z_{k}$. Using that $z_{k}$ is an ancestor
of $x_{k}$, we obtain

$f(x_{k})=f(z_{k})+L_{w}(\gamma_{x_{k}})-L_{w}(\gamma_{z_{k}})=f(y_{n_{k}})+d_{w}(y_{n_{k}},x_{k}).$

∎

######  Remark.

In the previous proof we used the following observation utilizing that $(X,b)$
is a tree and $\sigma$ is a path metric: For every $x\in\partial_{\sigma}X$
and every sequence $(x_{n})$ in $X$ converging to $x$ there exists a monotone
path $(y_{n})$ converging to $x$ such that any $x_{n}$ has an element from the
path $(y_{n})$ as an ancestor.

##  4\. Recurrence and intrinsic metrics

In this section we use similar technics as in Section 3 to give a new
characterization of recurrence in terms of intrinsic metrics and to study the
relation of recurrence to the vanishing of the capacity of the boundary.
Moreover, we provide an alternative proof for a classical characterization of
recurrence due to Yamasaki. For general background on recurrence we refer the
reader to the textbooks [12, 26].

The word recurrence stems from the stochastic perspective. In this perspective
the graph gives rise to a Markov process modeling a particle jumping between
the points of $X$. Recurrence then describes the phenomenon that the particle
comes back to any point of $X$ again and again. In the analytic description,
which is our concern here, this is encoded by various forms of irrelevance of
what is happening far away (i.e. outside of finite sets). We will see precise
versions as we go along and this is the main topic of this section.

######  Definition 4.1 (Recurrence).

A graph $G=(X,b)$ is called _recurrent_ if the constant function $1$ is
contained in $\mathfrak{D}_{0}(G)$. Graphs that are not recurrent are called
_transient_.

######  Remark.

  1. (a)

The definition of recurrence means that there exists a sequence of functions
$(f_{n})$ in $C_{c}(X)$ with $f_{n}\to 1$ pointwise and
$Q(f_{n})=Q(f_{n}-1)\to 0,n\to\infty$. As the $f_{n}$ have finite support this
can be seen as an instance of how the behaviour outside of compact sets (in
this case the supports of the $f_{n}$) becomes irrelevant.

  2. (b)

Recurrence is equivalent to $\mathfrak{D}_{0}(G)=\mathfrak{D}(G)$, i.e.,
$C_{c}(X)$ being dense in $\mathfrak{D}(G)$ with respect to the norm
$\left\|\cdot\right\|_{o}$, see e.g.[22, Theorem 3.63].

  3. (c)

For disconnected graphs transience is a stronger property than not being
recurrent. Since all the graphs in this paper are assumed to be connected, we
may well use the above definition. For further background on recurrence we
refer the reader to [19].

Next we connect recurrence, vanishing of the capacity and finiteness of metric
balls, to the existence of certain unbounded functions of finite energy.

######  Theorem 4.2 (Characterization of recurrence).

Let $G=(X,b)$ be an infinite graph. The following conditions are equivalent:

  1. (i)

$G$ is recurrent.

  2. (ii)

There is a function of finite energy $f\in\mathfrak{D}(G)$ that satisfies

$\liminf_{x\rightarrow\infty}f(x)=\infty.$

  3. (iii)

There is an intrinsic metric $\sigma\in\mathfrak{M}(G)$ that induces the
discrete topology on $X$ such that distance balls with respect to $\sigma$ are
finite.

  4. (iii)’

There exists a finite measure $m$ and an edge weight $w$ adapted to it such
that the distance balls with respect to $d_{w}$ are finite.

  5. (iv)

For one (every) finite measure $m$ on $X$ and one (every) compactification $Y$
of $X$ the equality ${\rm cap}_{m}(\partial_{Y}X)=0$ holds.

  6. (v)

One (every) finite measure has the following feature: For any $\varepsilon>$
there exists a finite set $F$ in $X$ with ${\rm cap}_{m}(X\setminus F)=0$.

###### Proof.

(i) $\Rightarrow$ (iv): Let $m$ be an arbitrary finite measure on $X$ and $Y$
a compactification of $X$. By (i) there exists a sequence $(f_{n})$ in
$C_{c}(X)$ with $f_{n}\to 1$ pointwise and $Q(f_{n})\to 0$. Replacing $f_{n}$
by $(f_{n}\vee 0)\wedge 1$ we can assume without loss of generality $0\leq
f_{n}\leq 1$ for each $n$. Then, $0\leq 1-f_{n}\leq 1$ holds and $1-f_{n}$ is
$1$ outside the finite support of $f_{n}$. Hence,

${\rm cap}_{m}(\partial_{Y}X)\leq Q(1-f_{n})+\left|1-f_{n}\right|_{m}^{2}$

holds for each $n$. It suffices to show that both terms on the right hand side
converge to zero. The first term satisfies $Q(1-f_{n})=Q(f_{n})\to
0,n\to\infty$. The second term satisfies $\left|1-f_{n}\right|_{m}^{2}\to
0,n\to\infty$ by Lebesgue theorem on dominated convergence (as $0\leq
1-f_{n}\leq 1$ holds and $1-f_{n}$ converges pointwise to $0$ and $m$ is a
finite measure).

(iv) $\Rightarrow$ (ii): : This follows by a straightforward adaption of the
proof of (i)$\Rightarrow$ (iii) of Lemma 3.3.

(ii) $\Rightarrow$ (iii): Let $f$ be a function satisfying (ii). By
Proposition 2.6 we can assume without loss of generality that the values of
$f$ are pairwise distinct. Set $\sigma(x,y)=\sigma_{f}(x,y)=|f(x)-f(y)|$ for
all $x,y\in X$. This yields a pseudo metric that is intrinsic with respect to
a finite measure, see Lemma 2.4. In fact, it is even a metric as the values of
$f$ are pairwise distinct. Its distance balls are given by

$B_{r}^{\sigma}(o)=\\{x\in X\mid f(o)-r\leq f(x)\leq r+f(o)\\}.$

Since $\liminf_{x\rightarrow\infty}f(x)=\infty,$ they are finite. In
particular, this metric induces the discrete topology.

(iii) $\Rightarrow$ (i): Let an intrinsic metric $\sigma$ with respect to a
finite measure $m$ be given according to (iii). Hence, $\sigma$ induces the
discrete topology and its distance balls are finite. Now, let $F$ be an
arbitrary finite set. Then, $\sigma_{F}:=\sigma(\cdot,F)$ satisfies

  * •

$\sigma_{F}=0$ on $F$.

  * •

$\sigma_{F}\geq 1$ outside of $F_{1}:=\\{x\in X:\sigma(F,x)<1\\}$ and $F_{1}$
is finite (as $F$ is a finite set and distance balls with respect to $\sigma$
are finite).

Define $g_{F}:=(1-\sigma_{F})_{+}$. Then $g_{F}$ equals to $1$ on $F$ (by the
first bullet point) and has finite support contained in $F_{1}$ (by the second
bullet point). Moreover, as $Q$ is compatible with contractions and $Q(1)=0$
holds we find from Lemma 2.4 the estimate

$Q(g_{F})\leq Q(1-\sigma_{F})=Q(\sigma_{F})\leq 2m(X\setminus F).$

So, choosing an increasing sequence $(F_{n})$ of finite sets with
$\cup_{n}F_{n}=X$ we obtain a sequence $f_{n}:=g_{F_{n}}$ in $C_{c}(X)$
converging pointwise to $1$ with

$Q(f_{n})\leq 2m(X\setminus F_{n})\to 0,n\to\infty.$

This shows (i).

The equivalence between (iv) and (v) is clear.

(iii)’ $\Rightarrow$ (iii): By Lemma 2.7 the metric $d_{w}$ is intrinsic with
respect to the finite measure $m$. To show that it induces the discrete
topology we note that finiteness of $d_{w}$-balls implies that for all $R>0$
and $x\in X$ the set

$\\{y\in X\mid y\sim x\text{ with }w(x,y)<R\\}$

is finite (otherwise the $R$-ball around $x$ would contain infinitely many
points). This is known as essential local finiteness of $w$ and, according to
[13, Lemma 2.2], implies that $d_{w}$ induces the discrete topology.

(iii) $\Rightarrow$ (iii)’: We choose $w:=\sigma$. Then, $w$ is adapted to a
finite measure $m$ and $d_{\sigma}$ is then an intrinsic metric with respect
to $m$ with $\sigma\leq d_{\sigma}$ by Lemma 2.7. In particular, balls with
respect to $d_{w}$ are contained in the corresponding balls with respect to
$\sigma$ and are, hence, finite. ∎

######  Remark.

  1. (a)

The equivalence between (i) and (iv) can be seen as a special instance of the
recurrence theory developed by the third author in his (unpublished) PhD
thesis [21].

  2. (b)

Clearly, a metric with finite distance balls must induce the discrete
topology.

  3. (c)

In the proof of (ii) $\Rightarrow$ (iii) we have seen that for $f$ of finite
energy with $\liminf_{x\to\infty}f(x)=\infty$ the intrinsic (pseudo)metric
$\sigma_{f}$ has finite distance balls. There is a converse of sorts to this:
Let $\sigma$ be a metric and define for $x\in X$ the function $f_{x}$ by
$f_{x}(y):=\sigma(y,\\{x\\})$. Then, the distance balls around one $x\in X$
are finite if and only if the distance balls around any $x\in X$ are finite
and this holds if and only if $\liminf_{y\to\infty}f_{x}(y)=\infty$ holds for
one (all) $x\in X$.

  4. (d)

The proof of (iii) $\Rightarrow$ (i) only uses that the balls of radius $1$
are finite. In fact, the number $1$ is irrelevant. It suffices that there is
an $r>0$ such that all balls of radius $r$ are finite. However, if $\sigma$ is
an intrinsic metric all of whose distance balls of radius $r$ are finite then
for any sequence $F_{n}$ of finite sets in $X$ with $F_{n}\subseteq F_{n+1}$
and $\cup F_{n}=X$ we can define $f:=\sum_{n=1}^{\infty}\sigma(F_{n},\cdot)$.
Then, $f$ will be well-defined with $\liminf_{x\to\infty}f(x)=\infty$ (by
finiteness of $r$-balls). With a suitable choice of $F_{n}$ then $f$ will have
finite energy and $\sigma+\sigma_{f}$ will be an intrinsic metric with respect
to a finite measure that has finite distance balls.

  5. (e)

The existence of an intrinsic metric with respect to a (finite) measure $m$
that has finite distance balls has strong consequences. In particular, as
observed in [8], it implies that associated graph Laplacians on
$\ell^{2}(X,m)$ (and more general magnetic Schrödinger operators [7, 20]) are
essentially self-adjoint. It is somewhat surprising that recurrence implies
essential self-adjointness for a particular finite measure, as in general
recurrence is strictly weaker than essential self-adjointness for all finite
measures. We refer to discussion after Theorem 11.6.15 in the survey [20].
This survey contains a version of the previous theorem, which was first
obtained in the second author’s master’s thesis [17].

We are now going to derive some consequence of the preceding theorem. As a a
first consequence of it we obtain an alternative proof for the (by now)
classical recurrence criterion of Yamasaki [28].

######  Corollary 4.3 (Yamasaki’s criterion).

Let $G=(X,b)$ be a locally finite graph. Then $G$ is recurrent if and only if
the set of all infinite paths is null.

###### Proof.

Let $G$ be recurrent. According to Theorem 4.2 there exists a finite measure
$m$ and a weight $w$ adapted to $m$ such that the intrinsic path metric
$d_{w}$ has finite distance balls. As $w$ is adapted to $m$ we have

$\sum_{x,y}b(x,y)w(x,y)^{2}\leq 2m(X)<\infty.$

It suffices to show that the length $L_{w}(\gamma)$ of any infinite path is
$\infty$. We consider two cases:

Case 1: The path $\gamma$ leaves any finite set. Then, the path leaves in
particular any ball of finite radius (w.r.t. $d_{w}$). Hence, the path must
have infinite length (as the metric is a path metric).

Case 2: The path $\gamma$ stays within a fixed finite set. Then, it must have
infinite length anyway.

Suppose that the set of all infinite paths is null and let $w$ be a
corresponding edge weight. The summability condition on $w$ implies that

$m_{w}(x):=\frac{1}{2}\sum\limits_{y\in X}b(x,y)w(x,y)^{2}$

is a finite measure. We consider the path metric $d_{w}$ induced by $w$. Lemma
2.7 (a) ensures that it is intrinsic with respect to $m_{w}$. Thus, $d_{w}$ is
an intrinsic metric with respect to a finite measure. Since all infinite paths
have infinite length, Theorem 2.10 implies that $d_{w}$ has finite distance
balls. This yields recurrence by Theorem 4.2. ∎

######  Remark.

For proving nullity of the set of all paths on recurrent graphs we did not use
local finiteness.

Another consequence of our characterization of recurrence is vanishing of the
capacity of all boundaries of metric completions in the recurrent case.

######  Corollary 4.4.

Let $G=(X,b)$ be a recurrent infinite graph. For any finite measure $m$ on $X$
and any metric $\sigma$ on $X$ that induces the discrete topology we have

${\rm cap}_{m}(\partial_{\sigma}X)\leavevmode\nobreak\ =\leavevmode\nobreak\
0.$

###### Proof.

This follows immediately from (v) of the previous theorem as
$\partial_{\sigma}X$ is contained in $X\setminus F$ for any finite $F$. ∎

In some cases the vanishing of the capacity of the boundary is equivalent to
recurrence. For this one needs that $\sigma$ is intrinsic with respect to the
finite measure $m$ and some more geometric data. In the following theorem we
discuss two situations where this is the case.

######  Theorem 4.5 (Capacity criterion).

Let $G=(X,b)$ be a graph. Let $\sigma$ be a metric that induces the discrete
topology and is intrinsic with respect to a finite measure $m$. Then $G$ is
recurrent if ${\rm cap}_{m}(\partial_{\sigma}X)=0$ and one of the following
conditions is satisfied:

  1. (a)

$G$ is locally finite.

  2. (b)

$(X,\sigma)$ is totally bounded.

###### Proof.

(a): According to Theorem 4.2 it suffices to construct an intrinsic metric $e$
with respect to a finite measure that has finite distance balls and induces
the discrete topology on $X$. The metric $e$ that we construct is a path
metric. Since $G$ is locally finite, it automatically induces the discrete
topology. By the discrete Hopf-Rinow theorem, Theorem 2.10, the finiteness of
distance balls is equivalent to the completeness of $(X,e)$. According to
Lemma 3.3 the assumption ${\rm cap}_{m}(\partial_{\sigma}X)=0$ yields a
function $f\in\mathfrak{D}(G)$ with
$\liminf_{x\rightarrow\partial_{\sigma}X}f(x)=\infty.$ We let
$e:=d_{\sigma+\sigma_{f}}$ be the path metric that is induced by the weight
$\sigma+\sigma_{f}$ with $\sigma_{f}(x,y)=|f(x)-f(y)|$. Lemma 2.5 shows that
the pseudometric $\sigma_{f}$ is intrinsic with respect to a finite measure
and so $\sigma+\sigma_{f}$ is intrinsic with respect to a finite measure. We
infer from Lemma 2.7 that also the induced path metric $e$ is intrinsic with
respect to a finite measure.

It remains to show the completeness of $(X,e)$. Let $(x_{n})$ be Cauchy with
respect to $e$. Lemma 2.7 yields $e\geq\sigma+\sigma_{f}\geq\sigma$, so that
$(x_{n})$ must also be a Cauchy sequence with respect to $\sigma$. Due to
completeness it has a limit $x\in\overline{X}^{\sigma}$. We show that $x\in X$
and that $(x_{n})$ also converges to $x$ with respect to $e$ by considering
two cases:

Case 1: $x\in\partial_{\sigma}X$:
$\liminf\limits_{y\rightarrow\partial_{\sigma}X}f(y)=\infty$ yields
$\liminf\limits_{n\to\infty}f(x_{n})=\infty$, so that for each
$m\in\mathbb{N}$

$e(x_{m},x_{n})\geq\sigma_{f}(x_{n},x_{m})=|f(x_{n})-f(x_{m})|$

is unbounded in $n$. In particular, this contradicts the assumption that
$(x_{n})$ is Cauchy with respect to $e$.

Case 2: $x\in X$: Since $\sigma$ induces the discrete topology on $X$,
convergence with respect to $\sigma$ to some point in $X$ yields that
$(x_{n})$ must eventually be constant. Hence, it also converges with respect
to $e$.

(b): By assumption $\overline{X}^{\sigma}$ is compact. Hence, vanishing
capacity of $\partial_{\sigma}X$ implies recurrence by Theorem 4.2. ∎

######  Remark.

  1. (a)

Part (a) of this Theorem is a generalization of [8, Theorem 3], which only
treats certain path metrics. Note that for finite underlying measures the
equality $D(Q)=D(Q^{\rm max})$ discussed in this reference is equivalent to
recurrence, see e.g. [19, Theorem 6.5].

  2. (b)

The condition of $(X,\sigma)$ being totally bounded means that it can be
isometrically embedded into a compact metric space. Below we consider examples
of bounded discrete $X\subseteq{\mathbb{R}}^{2}$ equipped with the Euclidean
metric.

  3. (c)

For general graphs it remains an open question whether or not the previous
theorem is true.

  4. (d)

For locally finite $G=(X,b)$ we established the equivalence of the following
assertions.

    1. (i)

$G$ is recurrent.

    2. (ii)

For one/all intrinsic metrics $\sigma$ with respect to a finite measure $m$
that induce the discrete topology we have

${\rm cap}_{m}(\partial_{\sigma}X)=0.$

    3. (iii)

The set of all infinite paths is null.

The implication (iii) $\Rightarrow$ (ii) can be seen as a sort of converse to
Theorem 3.6 when considering the set $A=\partial_{\sigma}X$.

##  5\. Resolvable graphs and harmonic functions

In this section we turn to the study of transient graphs. By the results of
the last section, transience is characterized by positivity of the capacity of
(suitable) boundaries. Here, we turn to a different aspect based on a
characterization of recurrence and transience in terms of superharmonic
functions (read on for the precise definition). Specifically, a graph is
transient if and only if it admits non-constant superharmonic functions of
finite energy (see e.g. [12]). In general, these superharmonic functions will
not be harmonic. This stimulates interest in those (transient) graphs which
admit non-constant harmonic functions of finite energy. The aim of this
section is to derive a capacity based sufficient condition for existence of
such functions. To this end, we introduce strong resolvability for graphs,
which is a somewhat stronger property than resolvability that was introduced
in [2]. We prove that (most) transient strongly resolvable graphs admit
harmonic functions.

######  Definition 5.1 (Resolvability).

A graph $G=(X,b)$ is called _resolvable_ if there is an edge weight $w$ with

$\sum_{x,y\in X}b(x,y)w(x,y)^{2}<\infty$

such that for every point $x\in\partial_{d_{w}}X$ the set of paths converging
to $x$ with respect to $d_{w}$ is null. In this case, $w$ is called a
_resolving weight_ for $G$.

The previous definition relied on the concept of path. We now aim at a path-
free definition which captures essentially the same concept. This yields the
following definition.

######  Definition 5.2 (Strong resolvability).

A graph $G=(X,b)$ is called _strongly resolvable_ , if there exists an
intrinsic metric $\sigma$ with respect to a finite measure $m$ that induces
the discrete topology such that ${\rm cap}_{m}(\\{x\\})=0$ for all
$x\in\partial_{\sigma}X$. In this case, $\sigma$ is called a _resolving
metric_ for $G$.

######  Proposition 5.3.

A strongly resolvable graph is resolvable.

###### Proof.

Let $\sigma$ be a resolving metric for $G$ that is intrinsic with respect to
the finite measure $m$. By Lemma 2.7, the path metric $d_{\sigma}$ induced by
$\sigma$ satisfies $\sigma\leq d_{\sigma}$. Hence, there is a continuous map
$\iota\colon\overline{X}^{d_{\sigma}}\to\overline{X}^{\sigma}$ that extends
the identity on $X$.

Let $x\in\partial_{d_{\sigma}}X$. We first show that
$\iota(x)\in\partial_{\sigma}X$. Suppose that this is not the case, i.e.
$\iota(x)\in X$. We choose a sequence $(x_{n})$ in $X$ with $x_{n}\to x$ with
respect to $d_{\sigma}$. Since $x_{n}\to\iota(x)$ with respect to $\sigma$ and
$\sigma$ induces the discrete topology, $(x_{n})$ must be eventually constant.
Hence, $x=\iota(x)\in X$, a contradiction.

Any path converging to $x$ with respect to $d_{\sigma}$ converges to
$\iota(x)$ with respect to $\sigma$. Hence, the set of all such paths is
contained in $\Gamma_{\\{\iota(x)\\},\sigma}$, the set of paths having
$\iota(x)$ as an accumulation point with respect to $\sigma$. It therefore
suffices to show that the latter set is null. Since
$\iota(x)\in\partial_{\sigma}X$, we have ${\rm cap}_{m}(\\{\iota(x)\\})=0$ by
assumption. Theorem 3.6 implies that $\Gamma_{\\{\iota(x)\\},\sigma}$ is null.
∎

######  Remark.

  1. (a)

Strong resolvability transfers the geometric notion of resolvability
introduced in [2] to a notion of potential theory. This has two advantages.
With strong resolvability one can also treat non-locally finite graphs, as
potential theory does not distinguish between locally finite and non-locally
finite graphs. This is an advantage of potential theory. Indeed, for notions
invoking infinite paths in general the non-locally finite case poses problems,
as e.g. the discrete Hopf-Rinow theorem 2.7 does not hold on non-locally
finite graphs, see the discussion in [8, Appendix A]. Moreover, strong
resolvability is also available on more general spaces that admit a potential
theory, e.g. Riemannian manifolds, fractals or metric graphs.

  2. (b)

As discussed after Theorem 3.6 we believe that ${\rm cap}_{m}(\\{x\\})=0$ for
all $x\in\partial_{\sigma}X$ is strictly stronger than
$\Gamma_{\\{x\\},\sigma}$ being null for all $x\in\partial_{\sigma}X$. Hence,
resolvability seems strictly stronger that resolvability (even though we do
not have concrete examples). However, below we shall see that planar graphs,
the main examples for resolvable graphs in [2], are also strongly resolvable.

######  Definition 5.4 ((Super)Harmonic functions).

Let $G=(X,b)$ be a graph. A function $f\colon X\to\mathbb{C}$ is called
superharmonic if for all $x\in X$ it satisfies

$f(x)\geq\frac{1}{{\rm deg}(x)}\sum_{y\in X}b(x,y)f(y),$

where we assume absolute convergence of the sum on the right side of the
equation. The function $f$ is called harmonic if both $f$ and $-f$ are
superharmonic. We write $\mathfrak{H}(G)$ for the space of harmonic functions.

An important property of these functions is that on transient graphs functions
of finite energy are uniquely represented as sums of harmonic functions of
finite energy and functions in $\mathfrak{D}_{0}(G)$, see Theorem 6.3 in [22]
for reference.

######  Theorem 5.5 (Royden decomposition).

Let $G=(X,b)$ be a transient graph. For all $f\in\mathfrak{D}(G)$ there exists
a unique $f_{0}\in\mathfrak{D}_{0}(G)$ and a unique harmonic
$f_{h}\in\mathfrak{D}(G)$ such that

$f=f_{0}+f_{h}$

and

$Q(f)=Q(f_{0})+Q(f_{h}).$

The function $f_{h}$ is the unique function in $\mathfrak{D}(G)$ that
satisfies

$Q(f_{h})=\inf\\{Q(f-g)\mid g\in\mathfrak{D}_{0}(G)\\}=\inf\\{Q(f-g)\mid g\in
C_{c}(X)\\}.$

Moreover, if $f$ is bounded, then $f_{0}$ and $f_{h}$ are bounded as well.

Resolvability was introduced to prove the existence of non-constant harmonic
functions on transient locally finite resolvable graphs. This result of
Benjamini and Schramm carries over to strongly resolvable graphs that need not
be locally finite. Before we prove this we need a result on harmonic functions
induced by Lipschitz functions.

Let $\sigma\in\mathfrak{M}(G)$ which is intrinsic with respect to the finite
measure $m$ and suppose now that $(X,b)$ is transient. Using the Royden
decomposition we define the map

$\Phi\colon\mathfrak{D}(G)\cap
C_{b}(\overline{X}^{\sigma})\to\mathfrak{D}(G)\cap\mathfrak{H}(G),\quad
f\mapsto f_{h}.$

Since the Royden decomposition preserves boundedness and $m$ is finite, we
even obtain that $\Phi$ maps to $H^{1}(G,m)$. The following is the main
observation in this section, which will be used to construct many non-constant
hamronic functions of finite energy.

######  Lemma 5.6.

Let $(X,b)$ be a graph and let $\sigma$ be an intrinsic metric with respect to
a finite measure $m$ that induces the discrete topology such that ${\rm
cap}_{m}(\partial_{\sigma}X)>0$. Moreover, let

$S=\\{x\in\partial_{\sigma}X\mid{\rm cap}_{m}(U\cap\partial_{\sigma}X)>0\text{
all open }x\in U\subseteq\overline{X}^{\sigma}\\}.$

Then

$\ker\Phi\subseteq\\{f\in\mathfrak{D}(G)\cap C_{b}(\overline{X}^{\sigma})\mid
f|_{S}=0\\}.$

In particular, if $\Phi(f)$ is constant, then $f$ is constant on $S$.

###### Proof.

Let $f\in\mathfrak{D}(G)\cap C_{b}(\overline{X}^{\sigma})$ with $f|_{S}\neq
0$. We show $f_{h}=\Phi(f)\neq 0$. Without loss of generality there exists
$\varepsilon>0$ such that $f(x)\geq\varepsilon$ for some $x\in S$. Using
Theorem 5.5 we choose a sequence $(g_{n})$ in $C_{c}(X)$ with
$Q(f_{h})=\inf_{n\geq 1}Q(f-g_{n})=\lim_{n\to\infty}Q(f-g_{n})$. As noted
above we have $f_{h}\in H^{1}(G,m)$.

Claim: The sequence $(g_{n})$ can be chosen such that $f-g_{n}\to f_{h}$ in
$H^{1}(G,m)$.

Proof of the claim. It suffices to show that $(g_{n})$ can be chosen such that
$f-g_{n}\to f_{h}$ in $\ell^{2}(X,m)$. We can assume
$\left\|g_{n}\right\|_{\infty}\leq 2\left\|f\right\|_{\infty}$, as otherwise
we could write

$((f-g_{n})\wedge\left\|f\right\|_{\infty})\vee(-\left\|f\right\|_{\infty})=f-h_{n}$

with appropriate $h_{n}\in C_{c}(X)$. These satisfy
$\left\|h_{n}\right\|_{\infty}\leq 2\left\|f\right\|_{\infty}$ and, using the
compatibility of $Q$ with contractions, also

$Q(f_{h})\leq Q(f-h_{n})\leq Q(f-g_{n}).$

Now assume $(g_{n})$ is chosen with $\left\|g_{n}\right\|_{\infty}\leq
2\left\|f\right\|_{\infty}$. The Royden decomposition shows $Q(f_{0}-g_{n})\to
0$. Moreover, our assumption ${\rm cap}_{m}(\partial_{\sigma}X)>0$ implies
transience of the graph, see Corollary 4.4. On transient graphs convergence on
$\mathfrak{D}_{0}(G)$ with respect to $Q$ implies pointwise convergence, see
e.g. [11, Theorem B.2]. Hence, we obtain $f_{0}-g_{n}\to 0$ pointwise, which
implies $f-g_{n}\to f_{h}$ pointwise. Since the functions $f-g_{n}$ are
uniformly bounded by $3\left\|f\right\|_{\infty}$ and since $m$ is a finite
measure, Lebesgue’s dominated convergence theorem yields $f-g_{n}\to f_{h}$ in
$\ell^{2}(X,m)$, which shows the claim.

Let now $(g_{n})$ be a sequence as in the claim. Since $\sigma$ induces the
discrete topology, the compactly supported function $g_{n}$ can be
continuously extended to $\overline{X}^{\sigma}$ by letting $g_{n}=0$ on
$\partial_{\sigma}X$. Then $f-g_{n}$ is continuous on $\overline{X}^{\sigma}$
with $f-g_{n}=f$ on $\partial_{\sigma}X$. By the continuity of $f$ there
exists a relatively open neighborhood $U_{x}\subseteq\partial_{\sigma}X$ of
$x$ in $\partial_{\sigma}X$ with $f-g_{n}=f\geq\varepsilon/2$ on $U_{x}$ for
all $n\in{\mathbb{N}}$. Using that $x\in S$ we obtain ${\rm
cap}_{m}(U_{x})>0$. By the continuity of $f-g_{n}$ there exists an open
$O_{n}\subseteq\overline{X}^{\sigma}$ with $U_{x}\subseteq O_{n}$ and
$f-g_{n}\geq\varepsilon/4$ on $O_{n}$ such that $4(f-g_{n})/\varepsilon\geq 1$
on $X\cap O_{n}$. The way the capacity is defined for subsets of the boundary
yields

$\frac{16}{\varepsilon^{2}}\left\|f-g_{n}\right\|^{2}_{Q,m}\geq{\rm
cap}_{m}(X\cap O_{n})\geq{\rm cap}_{m}(U_{x}).$

Using $f-g_{n}\to f_{h}$ in $H^{1}(G,m)$, we obtain

$\left\|f_{h}\right\|^{2}_{Q,m}=\lim_{n\to\infty}\left\|f-g_{n}\right\|_{Q,m}^{2}\geq\frac{\varepsilon^{2}}{16}{\rm
cap}_{m}(U_{x})>0$

and arrive at $f_{h}\neq 0$.

For the ’In particular’-part assume that $\Phi(f)$ is constant equal to $C$.
Since the harmonic part of a constant function is just the constant function
itself, we obtain $\Phi(f-C)=\Phi(f)-C=0$. Hence, what we previously proved
shows $f=C$ on $S$. ∎

######  Remark.

The set $S$ in this lemma is the support of the outer measure ${\rm cap}_{m}$
restricted to subsets of $\partial_{\sigma}X$.

Assume $\sigma\in\mathfrak{M}(G)$ is intrinsic with respect to the finite
measure $m$. We denote the set of bounded Lipschitz functions with respect to
$\sigma$ by ${\rm Lip}_{b}(X)={\rm Lip}_{b,\sigma}(X)$. If $f\in{\rm
Lip}_{b}(X)$, then Lemma 2.4 shows that $f\in H^{1}(G,m)$ (the lemma implies
$f\in\mathfrak{D}(G)$ and the boundedness of $f$ yields $f\in\ell^{2}(X,m)$).
Moreover, $f$ can be uniquely extended to a Lipschitz function
$\overline{X}^{\sigma}$, which we also denote by $f$ with a slight abuse of
notation. Hence, ${\rm Lip}_{b}(X)\subseteq\mathfrak{D}(G)\cap
C(\overline{X}^{\sigma})$. This observation is used in the proof of the
following theorem.

######  Theorem 5.7.

Let $(X,b)$ be a graph and let $\sigma$ be an intrinsic metric with respect to
a finite measure $m$ that induces the discrete topology such that ${\rm
cap}_{m}(\partial_{\sigma}X)>0$. Moreover, let

$S=\\{x\in\partial_{\sigma}X\mid{\rm cap}_{m}(U\cap\partial_{\sigma}X)>0\text{
all open }x\in U\subseteq\overline{X}^{\sigma}\\}.$

Then $\dim(\mathfrak{D}(G)\cap\mathfrak{H}(G))\geq|S|$. In particular, if
$|S|\geq 2$, then the graph admits a non-constant harmonic function of finite
energy.

###### Proof.

Without loss of generality we can assume $|S|\geq 2$ for otherwise the
statement is trivial because constant functions belong to
$\mathfrak{D}(G)\cap\mathfrak{H}(G)$. Let $f_{1},\ldots,f_{n}\in{\rm
Lip}_{b}(X)$. The previous lemma shows that if $f_{1}|_{S},\ldots,f_{n}|_{S}$
are linearly independent, then $\Phi(f_{1}),\ldots,\Phi(f_{n})$ are linearly
independent in $\mathfrak{D}(G)\cap\mathfrak{H}(G)$. With this at hand the
statement follows from $\dim{\rm Lip}_{b}(X)\geq\dim{\rm Lip}_{b}(S)\geq|S|$
(use that any bounded Lipschitz function on $S$ can be extended to a bounded
Lipschitz function on $\overline{X}^{\sigma}$). ∎

######  Corollary 5.8 (Existence of non-constant harmonic functions).

Let $G=(X,b)$ be a strongly resolvable graph and let $\sigma$ be a resolving
metric that is intrinsic with respect to the finite measure $m$. If ${\rm
cap}_{m}(\partial_{\sigma}X)>0$, then the space of bounded harmonic functions
of finite energy is infinite dimensional.

###### Proof.

Let $S$ be the support of the capacity on the boundary introduced in the
previous theorem. Its complement is given by

$\partial_{\sigma}X\setminus S=\\{x\in\partial_{\sigma}X\mid\text{ ex. open
}x\in U\subseteq\overline{X}^{\sigma}\text{ with }{\rm
cap}_{m}(U\cap\partial_{\sigma}X)=0\\}.$

Since $(\overline{X}^{\sigma},\sigma)$ is separable, its topology has a
countable basis. Hence, the $\sigma$-sub-additivity of ${\rm cap}_{m}$ yields
${\rm cap}_{m}(\partial_{\sigma}X\setminus S)=0$. Using the subadditivity of
the capacity again shows

${\rm cap}_{m}(S)={\rm cap}_{m}(\partial_{\sigma}X)>0.$

By our assumption every point in $S$ has capacity $0$. Hence, $S$ must be
uncountable for otherwise $\sigma$-subadditivity would imply ${\rm
cap}_{m}(S)=0$, which contradicts our previous considerations. With this at
hand the claim follows from the previous theorem. ∎

This theorem is a version of [2, Theorem 3.1] for strongly resolvable but
possibly non-locally finite graphs. We had to replace the transience
assumption of [2] by the stronger ${\rm cap}_{m}(\partial_{\sigma}X)>0$. As
discussed in Theorem 4.5, for some classes of graphs transience implies this
condition. We mention these situations in the following corollary.

######  Corollary 5.9.

Let $G=(X,b)$ be a transient, strongly resolvable graph and let one of the
following conditions be fulfilled:

  1. (a)

$G$ is locally finite.

  2. (b)

$\sigma$ is a resolving metric and $(X,\sigma)$ is totally bounded.

Then the space of bounded harmonic functions of finite energy is infinite
dimensional.

###### Proof.

By Theorem 4.5 both conditions imply ${\rm cap}_{m}(\partial_{\sigma}X)>0$
with respect to a resolving metric $\sigma$. Hence, the claim follows from the
previous corollary. ∎

Constructing harmonic functions from functions on a potential theoretic
boundary (the support of the capacity on the metric boundary) is reminiscent
of solving the Dirichlet problem. Under suitable additional conditions on the
graph and on the function on the boundary this can be made precise.

######  Remark (Solving the Dirichlet problem on $S$ for uniformly transient
graphs).

Let $(X,b)$ be a graph with $\mathfrak{D}_{0}(G)\subseteq C_{0}(X)$, where
$C_{0}(X)$ denotes the uniform closure of $C_{c}(X)$. Graphs with this
property are called uniformly transient. As the name suggests uniformly
transient graphs are transient, see [11] for this fact and further background
on uniform transience. Let $\sigma\in\mathfrak{M}(G)$ be intrinsic with
respect to the finite measure $m$ and let $S$ denote the support of the
capacity on the boundary discussed above. Then for any bounded Lipschitz
function $\varphi\colon S\to\mathbb{R}$ the Dirichlet problem

$\begin{cases}h\in\mathfrak{H}(G)\cap\mathfrak{D}(G)\\\ h\in
C_{b}\left(\overline{X}^{\sigma}\right)\text{ with }h|_{S}=\varphi\end{cases}$

has a unique solution.

Uniqueness: This follows directly from Lemma 5.6.

Existence: The bounded Lipschitz function $\varphi\colon S\to\mathbb{R}$ can
be extended to a bounded Lipschitz function
$f\colon\overline{X}^{\sigma}\to\mathbb{R}$. Consider the Royden decomposition
$f=f_{0}+f_{h}$ with $f_{0}\in\mathfrak{D}_{0}(G)\subseteq C_{0}(X)$ and
harmonic $f_{h}\in\mathfrak{D}(G)$. Any sequence in $X$ converging to a point
in $\partial_{\sigma}X$ must eventually leave any finite set. Hence, $f_{0}$
can be extended to a continuous function on $\overline{X}^{\sigma}$ by letting
$f_{0}=0$ on $\partial_{\sigma}X$. This shows that also $f_{h}=f-f_{0}$ has a
bounded continuous extension to $\overline{X}^{\sigma}$ with
$f_{h}|_{\partial_{\sigma}X}=f|_{\partial_{\sigma}X}$. By constructions this
yields $f_{h}|_{S}=\varphi$.

##  6\. Planar and canonically compactifiable graphs

In this section we show that circle packings of bounded geometry and hence
locally finite planar graphs of bounded geometry are always strongly
resolvable. Moreover, we prove that canonically compactifiable graphs are
never strongly resolvable showing that planar graphs of bounded geometry can
never be canonically compactifiable.

First we recall the notion of circle packings and their contact graphs. For an
extensive background on these topics we refer to the book [15].

######  Definition 6.1 (Circle packing and subordinated graphs).

A circle packing is a set $X\neq\emptyset$ and two maps $r\colon
X\to(0,\infty)$ and $\varphi\colon X\to{\mathbb{R}}^{2}$ such that the
collection of closed circles $C_{x}=B_{r(x)}(\varphi(x))$, $x\in X,$ in
${\mathbb{R}}^{2}$ satisfies $C_{x}^{\circ}\cap C_{y}^{\circ}=\emptyset$
whenever $x\neq y$. It is called bounded if $\bigcup_{x\in X}C_{x}$ is a
bounded set. An edge weight $b$ on $X$ is called subordinate to the circle
packing if $b(x,y)>0$ implies $C_{x}\cap C_{y}\neq\emptyset$.

######  Remark.

In what follows we simply write $C_{x},x\in X,$ to denote a circle packing.
The contact graph or nerve of a circle packing $C_{x},x\in X$, is the
combinatorial graph on $X$ with $x\sim y$ if $C_{x}\cap C_{y}\neq\emptyset$.
Hence, an edge weight $b$ on $X$ is subordinate to the circle packing if and
only if the induced discrete graph is a subgraph of the contact graph.

The following is our main observation in this section.

######  Theorem 6.2.

Let $C_{x},x\in X,$ be a bounded circle packing and suppose $(X,b)$ is
subordinate to the circle packing and has bounded geometry. Then $(X,b)$ is
strongly resolvable. In particular, if $(X,b)$ is transient, then it possesses
a non-constant harmonic function of finite energy.

###### Proof.

Let $\Omega=\sup_{x\in X}\deg(x)$. Then $\Omega<\infty$ due to $(X,b)$ having
bounded geometry. As above we let $r,\varphi$ denote the maps inducing the
circle packing. We consider the metric $\sigma$ on $X$ defined by
$\sigma(x,y)=|\varphi(x)-\varphi(y)|.$ We first show that $\sigma$ is an
intrinsic metric with respect to a finite measure inducing the discrete
topology.

The assumption $C_{x}\cap C_{y}\neq\emptyset$ for all $x\neq y$ implies

$\sigma(x,y)\geq r(x)+r(y)>r(x)$

for all $y\neq x$. Hence, $\sigma$ induces the discrete topology. Since $b$ is
subordinate to the circle packing, we also have $C_{x}\cap C_{y}\neq\emptyset$
whenver $x\sim y$. For $x\sim y$ this implies $\sigma(x,y)=r(x)+r(y)$. We
infer

$\displaystyle\sum_{x,y\in X}b(x,y)\sigma(x,y)^{2}$ $\displaystyle\leq
2\sum_{x,y\in X}b(x,y)(r(x)^{2}+r(y)^{2})$ $\displaystyle\leq
4\Omega\sum_{x\in X}r(x)^{2}$
$\displaystyle\leq\frac{4\Omega}{\pi}\lambda(A)<\infty,$

with $A=\bigcup_{x\in X}C_{x}$ and $\lambda$ the Lebesgue measure. This shows
that $\sigma$ is intrinsic with respect to a finite measure $m$.

Using that $\varphi$ is an isometry we identify $(X,\sigma)$ with $\varphi(X)$
in ${\mathbb{R}}^{2}$. In particular, the boundary with respect to $\sigma$ is
just the Euclidean boundary. Given $w\in\partial X$ we show ${\rm
cap}_{m}(\\{w\\})=0$. For $r>0$ we consider the function

$f_{r}\colon X\to{\mathbb{R}},\quad
f_{r}(x)=\left(2-\frac{|x-w|}{r}\right)_{+}\wedge 1.$

It satisfies $f_{r}=1$ on $B_{r}(w)\cap X$ and $f_{r}=0$ on $X\setminus
B_{2r}(w)$. Moreover, for $x\sim y$ we have

$|f_{r}(x)-f_{r}(y)|^{2}\leq\frac{|x-y|^{2}}{r^{2}}=\frac{(r(x)+r(y))^{2}}{r^{2}}.$

Next we compare $(r(x)+r(y))^{2}$ with $\lambda((C_{x}\cup C_{y})\cap
B_{2r}(w))$ as long as $x\sim y$ and $x,y\in B_{2r}(w)$. The boundary point
$w$ does not belong to the interior of the discs $C_{x},C_{y}$. This leads to
$r(x),r(y)\leq 2r$. Using this observation and that $C_{x},C_{y}$ are tangent,
we obtain

$\displaystyle\lambda((C_{x}\cup C_{y})\cap B_{2r}(w))$
$\displaystyle=\lambda(C_{x}\cap B_{2r}(w))+\lambda(C_{y}\cap B_{2r}(w))$
$\displaystyle\geq C(r(x)^{2}+r(y)^{2})$

for some constant $C>0$ independent of $x,y$ and $r$ (for the last inequality
we simply estimated the area of the intersection of two discs with the given
parameters). Combining these estimates we infer

$\displaystyle Q(f_{r})$ $\displaystyle\leq\frac{1}{2r^{2}}\sum_{x,y\in
X}b(x,y)(r(x)+r(y))^{2}$ $\displaystyle\leq\frac{1}{Cr^{2}}\sum_{x,y\in
X}b(x,y)\lambda((C_{x}\cup C_{y})\cap B_{2r}(w))$
$\displaystyle\leq\frac{2\Omega}{Cr^{2}}\lambda(B_{2r}(w))$
$\displaystyle\leq\frac{8\pi\Omega}{C}.$

Since $m$ is finite, we also have $\left\|f_{r}\right\|_{m}\to 0$, as $r\to
0+$. Both observations combined imply that $(f_{r})$ is bounded in the Hilbert
space $H^{1}(G,m)$. Using the Banach-Saks theorem we obtain a decreasing
sequence $r_{k}\to 0$ such that

$g_{n}=\frac{1}{n}\sum_{k=1}^{n}f_{r_{k}}$

converges in $H^{1}(G,m)$ to some $g\in H^{1}(G,m)$. Since convergence in
$H^{1}(G,m)$ implies $\ell^{2}(X,m)$-convergence and since $f_{r_{k}}\to 0$ in
$\ell^{2}(X,m)$, we obtain $g=0$. By construction we also have $g_{n}\geq 1$
on $B_{r_{n}}(w)$, which leads to

${\rm
cap}_{m}(\\{w\\})\leq\inf_{n\in{\mathbb{N}}}\left(Q(g_{n})+\left\|g_{n}\right\|^{2}_{m}\right)=0.$

The ’In particular’-part follows from Corollary 5.9 and the observation that
$(X,\sigma)$ is totally bounded as it is isometric to a bounded and hence
totally bounded subset of ${\mathbb{R}}^{2}$. ∎

######  Remark.

We do not assume local finiteness in the previous theorem. If $\bigcup_{x\in
X}C_{x}$ is not dense in ${\mathbb{R}}^{2}$, then the assumption on the
boundedness of the circle packing can be dropped. In this case, one just uses
inversion at a circle in the complement of $\bigcup_{x\in X}C_{x}$ to obtain a
bounded circle packing with isomorphic contact graph. For more details see
also the proof of the following corollary.

In the following corollary we call a weighted graph planar if the induced
combinatorial graph is planar (for a precise definition of the latter see e.g.
[14, Section 2.1]).

######  Corollary 6.3.

Let $G=(X,b)$ be a locally finite planar graph of bounded geometry. Then $G$
is strongly resolvable. In particular, if $G$ is transient, then $G$ possesses
a non-constant harmonic function of finite energy.

###### Proof.

According to Claim 4.3 in [15] any locally finite graph is isomorphic to the
contact graph of a circle packing. We show that the circle packing can be
chosen to be bounded. With this at hand the claim follows from the previous
theorem.

We add one additional point $o$ and one edge from $o$ to a point in $X$ such
that the resulting graph $(X^{\prime},b^{\prime})$ is still planar. According
to Claim 4.3 in [15] the graph $(X^{\prime},b^{\prime})$ is isomorphic to a
contact graph of a circle packing $C_{x},x\in X^{\prime}$. In order to make
this circle packing bounded, we use inversion at the circle $C_{o}$
corresponding to the new vertex $o$. We denote the inversion map by $\psi$.
Since inversions map circles to circles, $\psi(C_{x}),x\in X,$ is a circle
packing inside the bounded set $C_{o}$. By construction its contact graph is
the combinatorial graph underlying $(X,b)$. ∎

######  Remark.

The existence of non-trivial harmonic functions on transient planar graphs of
bounded geometry was one of the main results [2]. Subsequently, even more
explicit description of all harmonic functions of planar graphs were given via
boundaries of sphere packings [1] or square tilings [5]. For a unified
approach we refer to [9].

Recently the class of canonically compactifiable graphs (see below for a
definition) has gathered some attention. Our previous considerations allow us
to show that locally finite planar graphs of bounded geometry are never
canonically compactifiable.

According to [6] a graph $G=(X,b)$ is called canonically compactifiable if
$\mathfrak{D}(G)\subseteq\ell^{\infty}(X)$ (see [18] for different equivalent
characterizations as well). Examples are ${\mathbb{Z}}^{n}$ with $n\geq 3$,
see [11, Section 6], or graphs $(X,b)$ for which

$\sum_{x,y\in X}\frac{1}{b(x,y)}<\infty,$

see [6, Example 4.6]. Note that the latter condition implies very large vertex
degrees. We note the following.

######  Theorem 6.4.

Infinite canonically compactifiable graphs are not strongly resolvable. In
particular, locally finite infinite planar graphs of bounded geometry are not
canonically compactifiable.

###### Proof.

Let $(X,b)$ be an infinite canonically compactifiable graph and let $m$ be a
finite measure on $X$. Canonical compactifiability yields
$H^{1}(G,m)\subseteq\ell^{\infty}(X)$. The closed graph theorem implies the
existence of $C>0$ such that

$\left\|f\right\|_{\infty}^{2}\leq C(Q(f)+\left\|f\right\|_{m}^{2})$

for all $f\in H^{1}(G,m)$. This implies ${\rm cap}_{m}(U)\geq 1/C$ for any
$\emptyset\neq U\subseteq X$ such that points in any metric boundary have a
capacity at least $1/C$.

¸It remains to prove that for any intrinsic metric $\sigma$ with respect to
$m$, which induces the discrete topology, the space $(X,\sigma)$ is not
complete (and hence it has at least one boundary point). According to [18]
$(X,b)$ being canonically compactifiable and $\sigma$ being an intrisic metric
with respect to a finite measure imply that $(X,\sigma)$ is totally bounded.
Hence, $\overline{X}^{\sigma}$ is compact. But $(X,\sigma)$ is not compact as
an infinite set with the discrete topology. This shows
$\partial_{\sigma}X=\overline{X}^{\sigma}\setminus X\neq\emptyset$.

The ’In particular’-part follows from the previous corollary. ∎

## References

  * [1] Omer Angel, Martin T. Barlow, Ori Gurel-Gurevich, and Asaf Nachmias.  Boundaries of planar graphs, via circle packings.  Ann. Probab., 44(3):1956–1984, 2016.
  * [2] Itai Benjamini and Oded Schramm.  Harmonic functions on planar and almost planar graphs and manifolds, via circle packings.  Invent. math., 126:565–587, 1996.
  * [3] 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.
  * [4] Masatoshi Fukushima, Yoichi Oshima, and Masayoshi Takeda.  Dirichlet forms and symmetric Markov processes, volume 19 of de Gruyter Studies in Mathematics.  Walter de Gruyter & Co., Berlin, extended edition, 2011.
  * [5] Agelos Georgakopoulos.  The boundary of a square tiling of a graph coincides with the Poisson boundary.  Invent. Math., 203(3):773–821, 2016.
  * [6] Agelos Georgakopoulos, Sebastian Haeseler, Matthias Keller, Daniel Lenz, and Radosław K. Wojciechowski.  Graphs of finite measure.  J. Math. Pures Appl. (9), 103(5):1093–1131, 2015.
  * [7] Batu Güneysu, Matthias Keller, and Marcel Schmidt.  A Feynman-Kac-Itô formula for magnetic Schrödinger operators on graphs.  Probab. Theory Related Fields, 165(1-2):365–399, 2016.
  * [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] Tom Hutchcroft and Yuval Peres.  Boundaries of planar graphs: a unified approach.  Electron. J. Probab., 22:Paper No. 100, 20, 2017.
  * [10] 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.
  * [11] Matthias Keller, Daniel Lenz, Marcel Schmidt, and Radosław K. Wojciechowski.  Note on uniformly transient graphs.  Rev. Mat. Iberoam., 33(3):831–860, 2017.
  * [12] 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.
  * [13] Matthias Keller and Florentin Münch.  A new discrete Hopf-Rinow theorem.  Discrete Math., 342(9):2751–2757, 2019.
  * [14] Bojan Mohar and Carsten Thomassen.  Graphs on surfaces.  Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.
  * [15] Asaf Nachmias.  Planar maps, random walks and circle packing, volume 2243 of Lecture Notes in Mathematics.  Springer, Cham, 2020.  École d’été de probabilités de Saint-Flour XLVIII—2018, École d’Été de Probabilités de Saint-Flour. [Saint-Flour Probability Summer School].
  * [16] Tadashi Nakamura and Maretsugu Yamasaki.  Generalized extremal length of an infinite network.  Hiroshima Math. J., 6(1):95–111, 1976.
  * [17] Simon Puchert.  Resolvable graphs and harmonic functions, 2019.
  * [18] Simon Puchert.  Characterizations of canonically compactifiable graphs via intrinsic metrics and algebraic properties.  Arch. Math. (Basel), 116(5):541–549, 2021.
  * [19] Marcel Schmidt.  Global properties of Dirichlet forms on discrete spaces.  Dissertationes Math., 522:43, 2017.
  * [20] Marcel Schmidt.  On the existence and uniqueness of self-adjoint realizations of discrete (magnetic) Schrödinger operators.  In Analysis and geometry on graphs and manifolds, volume 461 of London Math. Soc. Lecture Note Ser., pages 250–327. Cambridge Univ. Press, Cambridge, 2020.
  * [21] Marcel Schmidt.  Energy forms.  PhD thesis, arXiv:1703.04883, Friedrich-Schiller-Universität Jena 2017.
  * [22] Paolo M. Soardi.  Potential theory on infinite networks, volume 1590 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 1994.
  * [23] Karl-Theodor Sturm.  Analysis on local Dirichlet spaces. I. Recurrence, conservativeness and $L^{p}$-Liouville properties.  J. Reine Angew. Math., 456:173–196, 1994.
  * [24] 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.
  * [25] Karl-Theodor Sturm.  Analysis on local Dirichlet spaces. III. The parabolic Harnack inequality.  J. Math. Pures Appl. (9), 75(3):273–297, 1996.
  * [26] Wolfgang Woess.  Random walks on infinite graphs and groups, volume 138 of Cambridge Tracts in Mathematics.  Cambridge University Press, Cambridge, 2000.
  * [27] Maretsugu Yamasaki.  Extremum problems on an infinite network.  Hiroshima Math. J., 5(2):223–250, 1975.
  * [28] Maretsugu Yamasaki.  Parabolic and hyperbolic infinite networks.  Hiroshima Math. J., 7(1):135–146, 1977.