{'fraction_non_alphanumeric': 0.060116959064327485, 'fraction_numerical': 0.01125858123569794, 'mean_word_length': 3.67996192289386, 'pattern_counts': {'":': 2, '<': 42, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graphs of finite measure

We consider weighted graphs with an infinite set of vertices. We show that boundedness of all functions of finite energy can be seen as a notion of `relative compactness' for such graphs and study sufficient and necessary conditions for this property in terms of various metrics. We then equip graphs satisfying this property with a finite measure and investigate the associated Laplacian and its semigroup. In this context, our results include the trace class property for the semigroup, uniqueness and existence of solutions to the Dirichlet problem with boundary arising from the natural compactification, an explicit description of the domain of the Dirichlet Laplacian, convergence of the heat semigroup for large times as well as stochastic incompleteness and transience of the corresponding random walk in continuous time.


Introduction
The study of the spectral and potential theory of infinite graphs has been a flourishing subject in recent years. In particular, the case of infinite graphs with possibly unbounded vertex degree has received substantial attention, e.g., [1,7,14,15,16,20,25,26,27,28,29,30,33,34,36,43,50,54,55] and references therein. In this paper, we want to contribute to this topic by having a closer look at a remarkable subclass of infinite graphs, namely, those which are 'relatively compact. ' Indeed, the subsequent considerations can be divided into two parts. In the first part, we present a class of graphs which have many claims to be considered as relatively compact in a natural sense. In the second part, we then study spectral, probabilistic and semigroup aspects of these graphs.
Let us discuss this in somewhat more detail and with the notation introduced and discussed in later sections. In fact, in order to provide here a concise overview, we will refrain from giving precise definitions but just indicate at which places they can be found in the paper.
We consider a countably infinite set X together with a graph structure (b, c). Here, b : X × X −→ [0, ∞) is symmetric, vanishes on the diagonal and satisfies the summability condition y∈X b(x, y) < ∞ for all x ∈ X. The function c : X → [0, ∞) is often assumed to be zero in the literature. Here, we mostly do not need c to vanish but can rather deal with summable c or even arbitrary c. A graph (b, c) over X naturally gives rise to a form Q on the domain D of functions of finite energy and the associated operator L (Section 2).
Our aim in the first part of the paper is to capture a situation in which the graph (b, c) over X can be considered to be relatively compact. Various (classes of) metrics have been considered on graphs (Section 3). First, there is a natural length structure, using the inverse of the edge weights b, giving rise to the metric d. This metric, and its completion, has found various applications, some of which are described in [15]. It has also recently appeared in the study of spectral properties, e.g., [7,20,50]. Another relevant metric is ̺. It is the square root of the well-known free effective resistance metric r (as shown below in Theorem 3.20). The free effective resistance plays an important role in the investigation of networks, see, e.g., the remarkable study of Kigami [39] or the influential textbook of Lyons/Peres [43] and recent work of Jorgensen/Pearse [29]. Here, we focus on ̺ rather than r, as it is very close in spirit to concepts found in both the geometry of Dirichlet spaces and non-commutative geometry. Indeed, it has already been studied in the context of graphs and non-commutative geometry by Davies in [9] and, very recently, it has appeared in a similar spirit in [23]. Finally, there are the so-called intrinsic metrics σ. They have been brought forward and first studied systematically in [12] (see [51] for earlier appearances as well). Subsequently, they have become a main tool in certain geometric and spectral theoretic considerations, see, e.g., [2,3,10,11,18,21,24,44,45]. They are always defined with respect to some measure m on X. In our situation, this measure should be finite as we want to deal with a relatively compact case.
Given this situation, each of the following statements seems to be a good candidate to express the relative compactness of the graph (b, c) over X: (A) X is totally bounded with respect to d.
(B) X is totally bounded with respect to ̺.
(C) X is totally bounded with respect to any metric σ which is intrinsic with respect to a finite measure. While these are certainly sensible requirements, they have the disadvantage that (A) and (B) are rather strong and (C) is hard to get a grip on.
On the other hand, letting D denote the functions of finite energy, there is the -at first seemingly -unrelated notion: (D) D consists only of bounded functions. In this case, there naturally appears a compactification K = X ∪∂X of X such that the closure of D can be realized canonically as an algebra of continuous functions on K (Subsection 4.2). This compactification K is obtained by C * -algebra techniques and turns out to coincide with the Royden compactification R (Theorem 4.11). Now, one of the main results of the first part of the paper shows that (when c ≡ As it is, therefore, both the most general and also a completely canonical way of phrasing the relative compactness of X, we single out graphs satisfying (D) as the canonically compactifiable ones.
Our corresponding considerations in Sections 3 and 4 also show that there are unique continuous maps extending the identity on X giving rise to the following chain of maps: This (and more) is summarized in Theorem 4.23. While there is no reason why these maps should be homeomorphisms in general, there is one prominent situation in which they are, namely, if c ≡ 0 and 1/b is summable, see Section 4.6.
Along the way, we also give a characterization of ̺ via intrinsic metrics in the case c ≡ 0 (Theorem 3.14) as well as various necessary and/or sufficient conditions for validity of the conditions (A), (B), (C) and (D) (Theorem 3.19, Theorem 4.3, Corollary 4.4 and Corollary 4.5).
The preceding considerations are the content of Sections 3 and 4. They give our treatment of what it means for a graph to be relatively compact. This is the first part of the paper.
The second part then deals with spectral, probabilistic and semigroup features of graphs satisfying (D).
More specifically, in Section 5, we first study selfadjoint Laplacians arising when graphs satisfying (D) are equipped with a finite measure. These operators are shown to have purely discrete spectrum. In fact, their resolvents and semigroups are shown to even be trace class (Section 5.1). We then study the Dirichlet problem on graphs satisfying (D) only, with no assumptions on the measure. Here, we show (in Section 5.2) that, for any continuous function ϕ on ∂X, there exists a unique f ∈ D satisfying Lf = 0 on X and f | ∂X = ϕ.
In Section 6, we then study convergence of the heat kernels for times tending to ∞.
Finally, in Section 7, we recall a result of [47] giving that for graphs (b, c) with c ≡ 0 over X equipped with a finite measure stochastic completeness, recurrence and the equality Q (D) = Q (N ) are all equivalent. We then use this to show that none of these properties hold if the graph additionally satisfies (D).
We are not aware of any work related to ours in the spirit of studying infinite, relatively compact graphs. However, of course, in terms of methods and intermediate results there are certainly points of contact to various works. This is discussed in the corresponding places in the paper. Here, we already want to mention the following: The idea of embedding a graph in a compact space K via C * -algebras (as done in our considerations below) has quite some history. It goes back at least to the work of Yamasaki [57] and Kayano and Yamasaki [31] (see the discussion in [48] as well). However, the focus of these works is completely different from ours. In these works, the corresponding constructions are carried out for arbitrary graphs (satisfying the assumption c ≡ 0), whereas we use it to single out the special class of graphs where D consists of bounded functions. For a recent treatment of how to embed a general Dirichlet space into a locally compact one, we refer the reader to [22].
Also, there is work of Carlson on the Dirichlet Problem, both for discrete graphs and for selfadjoint continuum Laplacians on metric graphs satisfying certain compactness type properties, which is somewhat similar to our considerations on the Dirichlet Problem [4,5] (see corresponding section for more detailed discussion).
Acknowledgements. D.L. and M.K. gratefully acknowledge partial support from the German Research Foundation (DFG). D.L. also takes the opportunity to thank Marcel Schmidt and Peter Stollmann for most useful discussions on a wide array of topics related to the present work and A. Teplyaev for pointing out some references. A substantial part of this work was done while D.L. was visiting the Department of Mathematics of Université Lyon 1 and the Department of Mathematics of Geneva University and he expresses his warmest thanks to these institutions. M.K. furthermore acknowledges the financial support of the ESF for the research stay at TU Graz where part of this work was done, the Golda Meir Fellowship, the Israel Science Foundation (grant no. 1105/10 and no. 225/10). R.W. would like to thank Józef Dodziuk for insightful discussions and acknowledges financial support provided by PSC-CUNY Awards, jointly funded by The Professional Staff Congress and The City University of New York. Furthermore, M.K., D.L., and R.W. would like to thank the organizers of the LMS EPSRC Durham Symposium on "Graph Theory and Interactions" and the generous hospitality of the Department of Mathematical Sciences at Durham University where the (almost) final parts of this work were carried out.
is symmetric, has zero diagonal, and satisfies y∈X b(x, y) < ∞ for all x ∈ X and c : X −→ [0, ∞) is arbitrary. We call X the vertex set, b the edge weight and c the killing term or potential. We say that x, y ∈ X are neighbors or connected by an edge of weight b(x, y), if b(x, y) > 0. If the number of neighbors of each vertex is finite, then we call (b, c) or b locally finite. A finite sequence (x 0 , . . . , x n ) of pairwise distinct vertices such that b(x i−1 , x i ) > 0 for i = 1, . . . , n is called a path from x 0 to x n . We say that (b, c) or b is connected if, for every two distinct vertices x, y ∈ X, there is a path from x to y.
All of our main results will assume that (b, c) is connected. This is mostly for convenience. By extending definitions properly and restricting attention to connected components, we could deal with the more general situation.
Often we will not only be given an infinite countable set X together with a weighted graph (b, c) but also a function m : X −→ [0, ∞). This function gives naturally rise to a measure on X via for A ⊆ X and we will not distinguish it from this measure. Then, (X, m) can be considered as a measure space and we will speak about graphs (b, c) over (X, m). For our applications to spectral theory we will then often assume that m does not vanish on any point. Moreover, the total mass m(X) = x∈X m(x) of X will appear prominently in various parts of our discussion.

Formal
Laplacians. Let C(X) be the space of complex valued functions on X and let C c (X) be the subspace of functions with finite support. Let ℓ 2 (X, m) be the complex Hilbert space of square summable functions equipped with the scalar product We may drop the subscript m and also write u, v = X uvm and denote the corresponding norm by · . We denote the space of bounded functions on X by ℓ ∞ (X) and denote by · ∞ the supremum norm. Given a weighted graph (b, c) over X we introduce the associated formal Laplacian L acting on If there is, furthermore, a positive measure m on X at our disposal, we will also consider the operator L = 1 m L acting as We can think of L and L as discrete analogues of the Laplace Beltrami operator on a Riemannian manifold plus a potential. We will be interested in properties of L and of its selfadjoint realizations. Note that f ∈ F satisfies Lf = 0 or Lf ≤ 0 or Lf ≥ 0 if and only if it satisfies the corresponding statements with L replaced by L for any positive measure m.

2.3.
Quadratic forms. Given a weighted graph (b, c) over X we define the generalized form Q : and define the generalized form domain by We think of Q(f ) as the energy of the function f and, accordingly, functions in D are said to have finite energy. Clearly, C c (X) ⊆ D as b(x, ·) is summable for every x ∈ X.
Since Q 1/2 is a seminorm and satisfies the parallelogram identity it gives, by polarization, a semi scalar product on D via In the case when c ≡ 0 and b is connected, the form Q defines a scalar product. Obviously, Q is compatible with normal contractions in the sense that Q(Cf ) ≤ Q(f ) holds for any f ∈ C(X) and any normal contraction C : C −→ C. (Here, C : C −→ C is a normal contraction if both |C(p)| ≤ |p| and |C(p) − C(q)| ≤ |p − q| hold for all p, q ∈ C. ) We now assume that we are additionally given a measure m on X of full support. Then, suitable restrictions of Q are in correspondence with certain selfadjoint restrictions of L on the Hilbert space ℓ 2 (X, m). This is discussed next: Let Q be a closed non-negative form on ℓ 2 (X, m) whose domain D = D(Q) satisfies C c (X) ⊆ D ⊆ D ∩ ℓ 2 (X, m) and which satisfies For such a form we define Q(u) := Q(u, u) for u ∈ D and Q(u) := ∞ for u ∈ D.
In [19,20] an 'integration by parts' was shown that allows one to pair functions in F and C c (X) via Q. More precisely, for f ∈ F and v ∈ C c (X) it was shown that where all sums converge absolutely. Moreover, it is shown there that D is a subset of F and that for f ∈ D the preceding sums all agree with Q(f, v). Note that this immediately gives for f ∈ F and v ∈ C c (X). By [20, Proposition 3.3] we then have that the self adjoint operator L associated to a form Q as above satisfies There are two natural examples, Q (N ) and Q (D) , which we refer to as the forms with Neumann and Dirichlet boundary conditions, respectively. The form Q (N ) has the domain We denote the corresponding self adjoint operators by L (N ) and L (D) . By construction, both Q (N ) and Q (D) are Dirichlet forms as Q is compatible with normal contractions. Moreover, Q (D) is regular, i.e., D(Q (D) )∩C c (X) is dense in D(Q (D) ) with respect to · Q and in C c (X) with respect to · ∞ .
The following basic lemma shows that all forms in question are sandwiched by the forms with Dirichlet and Neumann boundary conditions. Here, we write Proof. The 'only if' part of the statement is clear since Remark. Let us shortly comment on the role of c in our considerations. In the study of graphs, one usually sets c ≡ 0, i.e., one considers just a function b as defined above on a countable set X. Here, our point of view is different. We study regular Dirichlet forms on the measure space (X, m). These forms are naturally in one-to-one correspondence with graphs (b, c) as discussed in [33]. From this point of view, the appearance of c is quite natural. For the subsequent considerations, two regimes of c ≡ 0 can be distinguished. If 0 < x∈X c(x) < ∞, one can add a point ∞ to the graph and connect it to x ∈ X with an edge of weight c(x). In this way, one obtains a new graph without c and with one additional point. The relevant set of functions then consists of those vanishing on this additional point. If x∈X c(x) = ∞, such a construction is not possible. A more detailed description of this is given in Appendix A.

Analysis: The metrics ̺ and d and intrinsic metrics
The subsequent considerations deal with various aspects of metrics on graphs over discrete sets. The interplay between properties of the metric and the graph structure is the main focus.
We start by recalling some basic notation on metric spaces used throughout the section: As usual, for a space X with a metric δ we denote the completion of X with respect to δ by X δ . Obviously, δ can then be extended to a metric on X δ which will be denoted by the same letter. Also, we define the distance to a set A ⊂ X δ by The diameter of X with respect to δ is given by diam δ (X) := sup{δ(x, y) : x, y ∈ X}.
If the metric δ is understood from the context, we only write diamX for diam δ (X). The set of Lipschitz continuous functions on a metric space X is denoted by C Lip (X), where the dependence on the metric is suppressed.
As usual, a metric space is called totally bounded if, for any ε > 0, it can be covered by finitely many balls of radius ε. A metric space is compact if and only if it is totally bounded and complete.
In certain cases, it will also be convenient for us to be able to work with pseudometrics. A pseudometric on a set X is a function that satisfies all of the conditions of a metric, except that it may be zero outside of the diagonal. Whenever δ is a pseudometric on a set X, it will induce a metric δ on the set X which is the quotient of X arising from identifying points whose distance is zero. By a slight abuse of notation, we then denote the completion of X with respect to δ by X δ and refer to it as the completion of X with respect to δ.
3.1. The metrics d and ̺. In this subsection, we discuss two wellknown metrics on graphs. The metric d has featured prominently in the work of one of the authors [15] and has also played a role in the spectral theoretic considerations of [7,50]. The metric ̺ seems to be less known. It has played some role in work of Davies [9]. It is a very natural object from both the point of view of non-commutative geometry and that of Dirichlet forms (see remark below for further discussion).
In this subsection, we consider a weighted graph (b, c) over the discrete set X. Let us emphasize that our considerations do not require any measure m on X.
We fix a vertex o ∈ X and define a semi scalar product ·, · o on D by for f, g ∈ D and the corresponding semi norm If b is connected, then ·, · o defines a scalar product and · o defines a norm on D. We call D equipped with ·, · o the Yamasaki space after [57], where a first study of this space was undertaken (see later work of Soardi [48] for a systematic investigation as well).
Assume that b is connected. We define the functions ̺ and ̺ o on X × X by for x, y ∈ X. It is not hard to see that both ̺ and ̺ o are metrics. In fact, every defining feature of a metric is clear except for the finiteness of the values. This finiteness can easily be inferred from connectedness (an explicit bound is given below in Lemma 3.4). Clearly, all functions in D are Lipschitz continuous with respect to ̺ and ̺ o (with Lipschitz constant bounded by Q 1 2 (f ) and f o , respectively). The metric ̺ is essentially the smallest metric making all elements in D Lipschitz continuous with constant given by the respective values of the form.
Remarks.(a) Using the material presented below, it can be shown that in the definitions of ̺ and ̺ 0 the supremum can be replaced by a maximum. Indeed, the argument for ̺ o can be given as follows: Choose for x, y ∈ X a sequence f n with f n o ≤ 1 and ̺ o (x, y) = lim n→∞ |f n (x)−f n (y)|. Then, by Lemma 3.6, the sequence (f n (p)) must be bounded for any p ∈ X. By a standard diagonal sequence argument, we can then assume that (f n ) converges pointwise to a function f . This gives, in particular, Moreover, by Fatou's lemma and the pointwise convergence, we have Thus, the desired statement follows.
Note that the crucial ingredient in the above reasoning is to show pointwise boundedness of the sequence (f n ). If c ≡ 0, essentially the same argument works for ̺ (with the role of o played by any point p with c(p) > 0). If c ≡ 0, then each of the f n can be shifted by a constant. In particular, without loss of generality one can assume that f n (o) = 0 for all n. Now, the argument can be concluded as in the case of ̺ o (compare Proposition 3.1 as well).
(b) In Subection 3.3, we express ̺ in the terminology of electrical networks: it turns out that its square equals the free effective resistance. In this sense, the metric ̺ is essentially a variant of a well-known quantity in graph theory. From our point of view, it has two structural advantages over the free effective resistance: First of all, it is closely tied to the intrinsic metrics discussed in the next chapter, see, e.g., Theorem 3.14. Intrinsic metrics, in turn, are a key concept in the study of the geometry of Dirichlet forms. Moreover, its definition is close in spirit to non-commutative geometry. In fact, it has been considered in the context of non-commutative geometry and graphs by Davies in [9] and also, very recently, by Hinz / Kelleher / Teplyaev [23].
Obviously, ̺ o ≤ ̺ by definition. While the opposite inequality is wrong, it turns out that, in general, these two metrics are comparable, i.e., there is no need to distinguish between ̺ and ̺ o . This is the content of the next proposition.
For later use we also introduce the following notation. We introduce another family of metrics that emerge more directly from the geometry of the graph.
is called a length function if, for x, y ∈ X, the equality ℓ(x, y) = 0 holds if b(x, y) = 0 holds. Whenever ℓ is a length function and γ = (γ 0 , . . . , γ n ) is a path in X, the ℓ-length ℓ(γ) of γ is defined to be Remark. Note that we admit length functions ℓ with ℓ(x, y) = 0 even if b(x, y) > 0. This will simplify some considerations later on in the proof of Lemma 8.7. Let us emphasize, however, that these considerations would (with some additional effort) also work if we were to allow only length functions with ℓ(x, y) > 0 whenever b(x, y) > 0.
Any length function ℓ on a connected graph (b, c) gives rise to a pseudometric d ℓ defined via d ℓ (x, y) := inf{ℓ(γ) : γ is a path connecting x and y}.

Remark.
The assumption of connectedness of the graph forces that d ℓ (x, y) < ∞ for all x, y ∈ X. Likewise, ̺(x, y) < ∞ in this case, as follows from Lemma 3.4 below. If the graph is not connected, the above definitions will still give pseudometrics on each connected component. In the case that c ≡ 0, ̺(x, y) = ∞ for x and y in different connected components. Likewise, we can extend the definition of d ℓ to a function with values in [0, ∞] by setting it equal to ∞ on any two points which do not belong to the same connected component.
A natural choice of length functions is ℓ(x, y) = 1 b(x,y) s with a fixed parameter s > 0. The associated pseudometric is actually a metric (due to the summability assumption on b) and will be denoted by d s . For s = 1, we just write d instead of d 1 . Thus, we have : (x 0 , . . . , x n ) is a path from x to y}.
Let us remark that it is quite natural to consider the inverse of b(x, y) as a length since b(x, y) represents the strength of the interaction between two vertices. In this context, we also note that if edges are replaced by real intervals of that length, then Brownian motion on the resulting space corresponds to the Dirichlet form Q given above (see [16] for details). By a well-known inequality, we infer Remark. Given a measure m : X → (0, ∞), one obtains another natural length function, namely, Lengths of this type appear naturally when one deals with the unitary transformation f → m 1/2 f mapping the space D ∩ ℓ 2 (X, m) to the space D(Q m ) = D m ∩ ℓ 2 (X, 1). Here, D m are the functions of finite energy with respect to Q m where Q m is defined by m(x)m(y) and For this unitary transformation to be well defined, we need to assume < ∞ for all x ∈ X. Note that, in this procedure, the potential c m will not necessarily stay nonnegative and thus, in a certain sense, we leave the setting of discrete Dirichlet spaces we consider.
The following lemma shows that functions in D are 1 2 -Hölder continuous with respect to d.
Lemma 3.4. Let (b, c) be a connected graph over X. Then, for any f ∈ D and all x, y ∈ X, the inequality holds. In particular, ̺ 2 ≤ d and ̺ ≤ d 1/2 . If, in addition, c(x), c(y) > 0, then Proof. Take a path γ = (γ 0 , . . . , γ n ) from x to y. We estimate using the triangle inequality and the Cauchy-Schwarz inequality This implies the first statement of the lemma. The 'in particular' statement is then clear from the definition of ̺ and the already mentioned inequality d s ≤ d s . The second inequality follows directly from This finishes the proof.
Remark. The second inequality of the previous lemma shows that the distance ̺ might become much smaller than the distance d if the killing term c is nonzero. Moreover, a positive killing term gives rise to another length function defined by l c (x, y) = c(x) −1 + c(y) −1 if x and y are neighbors. We will show in Appendix A that one can construct a metric where both b and c are involved by introducing a virtual point at infinity. Lemma 3.4 has various consequences which we will now discuss. We start by considering completions of X. We recall that the completion of X with respect to a metric δ is denoted by X δ .
Theorem 3.5. Let (b, c) be a connected graph over X. Then, there exists a unique continuous map ι from X d to X ̺ extending the identity By continuity of ι, for any f ∈ D the function f (̺) • ι is a continuous function on X d which agrees with f on X. By the discussed uniqueness properties it must then agree with f (d) and the last statement of the theorem follows.
Let us mention that, in general, ι is not an embedding, i.e., it is not injective as can be seen from Example 8.9 in Section 8.
We start with a consequence of Lemma 3.4, namely, continuity of point evaluation for functions in D.
Lemma 3.6. If (b, c) is connected, then the point evaluation map is continuous for each x ∈ X.
Proof. Let x ∈ X and f, g ∈ D. Then, we estimate by the previous lemma This implies the statement of the lemma as d(x, o) < ∞ for all x whenever b is connected.
The previous important fact yields the following two well-known statements.
Proposition 3.7. If (b, c) is a connected graph over X, then the Yamasaki space ( D, ·, · o ) is a Hilbert space.
Proof. If (f n ) is a Cauchy sequence in ( D, ·, · o ), then (δ x f n ) converges to some f (x) ∈ C for each x ∈ X by the lemma above. Hence, (f n ) converges pointwise to a function f . By Fatou's lemma and the fact that (f n ) is a Cauchy sequence we get As (f n ) is a Cauchy sequence, another application of Fatou's lemma together with the pointwise convergence easily yields f − f n o → 0 as n −→ ∞. Proof. By the closed graph theorem, it suffices to show that A is a closed operator. As A is defined everywhere, it suffices to show that it is closable. Thus, we have to show that v ≡ 0 whenever (u n ) converges to 0 in B and (Au n ) converges to v ∈ D. This follows easily from the continuity property of A and the fact that point evaluation is continuous in D.

3.2.
Intrinsic metrics. Intrinsic metrics play an important role in the analysis of Laplacians on manifolds and -more generally -of strongly local Dirichlet forms [49]. For graphs (or general regular Dirichlet forms) this concept has only recently begun to be explored. In fact, they were only brought forward and first treated systematically in [12]. A fundamental idea of [12] is that a metric is intrinsic if and only if the associated set of Lipschitz functions belongs locally to the form domain with 'gradients' bounded by one (in a suitable sense). In our context, this translates to the definition given below. Further studies involving intrinsic metrics on graphs can now be found in various references, including [2,3,21,26]. We refer to these works for further discussion and references.
In this subsection, we are given a graph (b, c) over X and a measure m on X. Definition 3.9. Let (b, c) be a graph over (X, m). Then, a (pseudo)metric σ : holds.
Remark. Of course, the factor 1/2 in the previous definition does not play a particular role and could be replaced by any positive number. We use it as it simplifies some of the formulae given below. Also, with this factor, we are completely in line with [12] as well as with various subsequent works. Note, however, that some authors choose this factor to be one.
It can easily be seen by examples that σ can be unbounded even for a finite measure. At the end of this section, in Corollary 3.18, we give a geometric criterium which guarantees the boundedness of σ. Also, observe that, even if an intrinsic metric σ was allowed to take the value infinity, it would not do so on a connected graph. This follows by the definition of intrinsic and the triangle inequality, see Lemma 3.15 below.
A consequence of the above definition is that there is a strong connection between intrinsic (pseudo)metrics with respect to finite measures and functions in D. This is discussed in the subsequent two propositions.
The first proposition, which follows immediately from definitions, shows that any function in D gives rise to an intrinsic pseudometric with respect to a measure of total finite mass.
is an intrinsic pseudometric with respect to the measure M f defined by The next proposition gives a crucial ingredient in our considerations. It shows that intrinsic metrics belong to the domain of Q whenever the total mass of the space is finite.
Proposition 3.11. Let (b, c) be a graph over (X, m) with m(X) < ∞. Let σ be an intrinsic (pseudo)metric with respect to m and X σ the completion of X with respect to σ. Let U ⊆ X σ be given and consider the distance (a) If c ≡ 0, then σ U belongs to D and the estimate Proof. We only consider the case that σ is a metric. The case where it is a pseudometric can be treated analogously.
(a) By the triangle inequality and the definition of σ U we have, for any x, y ∈ X with b(x, y) > 0,

Now, a short calculation gives
This finishes the proof of part (a).
(b) This follows along very similar lines.
Proof. Let x ∈ X be arbitrary and consider the function f := 1 A σ {x} defining the distance to x scaled by the factor 1/A. Then, f belongs to D and satisfies Q(f ) ≤ 1 by the previous proposition. The definition of ̺ then gives, for any y ∈ X, the inequality This proves the statement.
The previous results allow one to establish strong relations between ̺ and intrinsic (pseudo)metrics. This is done in the next two theorems.
Theorem 3.13. Let (b, c) be a connected graph over (X, m) with m(X) < ∞. Let σ be an intrinsic (pseudo)metric with respect to m. Assume c ≡ 0 or C := x∈X c(x) < ∞ and boundedness of σ if c ≡ 0. Then, there exists a unique continuous map Proof. Uniqueness of the map is clear by the denseness of X in X ̺ .
Existence is a direct consequence of the previous proposition. Finally, the last statement on surjectivity and compactness of the range follows by standard arguments as already used in the proof of Theorem 3.5.
The previous theorem gives a relationship between ̺ and one intrinsic metric. In fact, it is possible to compute ̺ via intrinsic (pseudo)metrics. This is done next. Theorem 3.14. Let (b, c) be a connected graph over X with c ≡ 0. Then, Proof. Denote the function on the right hand side of the claimed equality by ̺ * . By Proposition 3.12, we have ̺ ≥ σ for any intrinsic (pseudo)metric with respect to a measure m with m(X) ≤ 1. This gives ̺ ≥ ̺ * .
Conversely, by Proposition 3.10, for any f ∈ D with Q(f ) ≤ 1 we obtain a pseudometric σ f which is intrinsic with respect to a measure The definition of ̺ then gives ̺ = sup{σ f : Q(f ) ≤ 1} and this implies ̺ ≤ ̺ * .
Remarks. (a) The theorem is in line with the ideas that ̺ is essentially the smallest metric making all functions in D Lipschitz continuous and that a metric is intrinsic if and only if all of its Lipschitz functions belong to the form domain with gradients uniformly bounded (in a certain sense).
(b) In the proof of the theorem we used σ f for f ∈ D. These are, in general, not metrics but pseudometrics. For this reason, we have taken the supremum in the theorem over pseudometrics. Let us note, however, that one could actually take the supremum over metrics as well. The reason is that any pseudometric of the form σ f can be made into an intrinsic metric by arbitrary small changes to f . This follows by a simple induction argument after one notices that for any x ∈ X and f ∈ D the function is continuous.
(c) In general, ̺ is not an intrinsic metric. This can be seen from Example 8.6. Indeed, in this example the underlying graph is relatively compact with respect to any intrinsic metric but is not relatively compact with respect to ̺. This also shows that, in general, the supremum above is not a maximum.
The following lemma provides a relationship between intrinsic metrics and d.
As usual, the minimum of two real numbers p and q is denoted by Lemma 3.15. Let (b, c) be a graph over (X, m) and σ an intrinsic metric. Then, for any path (x 0 , . . . , x n ) connecting x, y ∈ X, we have In particular, we then have Proof. We compute directly, using the triangle inequality and the intrinsic property, This shows the first claim. As for the second claim, we note that the Cauchy-Schwarz inequality directly gives Combining this inequality with the first statement, one can now easily obtain the second claim by squaring.
Remark. Let ℓ m (x, y) = m(x)m(y)/b(x, y) be the length function introduced earlier and d m,1/2 be the metric associated to the square root of this length function. Then, the lemma easily gives ) and then take the infimum over all corresponding paths.
We will next discuss various consequences of the previous lemma. As a first consequence, we obtain a condition for boundedness of intrinsic metrics on neighbors. In the case of trees even a converse is valid, see Section 8.
then every intrinsic metric is bounded on neighbors by a − 1 2 .
Proof. From Lemma 3.15 we infer that Hence, the statement follows.
We also get the following immediate estimate. We remark that, unlike in Proposition 3.12, we have no requirements on c (as c is neither involved in σ nor in d).
Corollary 3.17. Let (b, c) be a graph and σ an intrinsic metric for a finite measure m. Then, for all x, y ∈ X Proof. We obtain the statement by estimating m({x 0 , . . . , x n } ≤ m(X) in Lemma 3.15 and then taking the infimum over all paths.
As we see above, the assumption that an intrinsic metric σ is bounded whenever c does not vanish identically is important. Since for an intrinsic metric σ every (pseudo)metric σ ′ with σ ′ ≤ σ is obviously intrinsic as well, there always exist bounded intrinsic metrics. From Corollary 3.17 we now obtain directly the following criterion for boundedness of intrinsic metrics.
Then, every intrinsic metric with respect to a finite measure is bounded.
The corollary can be substantially strengthened in the case of locally finite graphs.
Then, X is totally bounded with respect to any metric which is intrinsic with respect to a finite measure.
Proof. Let m be a finite measure on X and σ be an intrinsic metric with respect to m. Chose ε > 0 arbitrary. We have to show that X can be covered by finitely many σ-balls with radius ε.
Fix an arbitrary vertex o ∈ X. For n ∈ N, denote by B n the set of all vertices in X which can be reached from o in not more than n-steps (i.e., those vertices x ∈ X for which there exist x 1 , . . . , x k ∈ X with k ≤ n, and x 1 = o, x k = x and b(x j , x j+1 ) > 0, j = 1, . . . , k − 1). Then, each B n is finite (as the graph is locally finite). Moreover, the union of the B n equals X. As m(X) is finite, we can now chose n large enough such that Set N := n + 1. Then, B N is finite.
Claim. Any point of X has σ distance to B N less than ε.
Proof of the claim: If the point p ∈ X belongs to B N this is clear. Otherwise, we can chose a path p = x 1 , . . . , x k = o from p to o such that k ≥ N + 1 and Let s ∈ {1, . . . , k} be the smallest integer such that x s belongs to B N .
Then, x s does not belong to B n (otherwise holds. Invoking Lemma 3.15, we now obtain Here, we used the definition of n in the last line. This proves the claim.
Due to local finiteness, the set B N is finite. Thus, the statement of the theorem follows from the claim.
3.3. Effective resistance and ̺ via electrical networks. In this subsection, we express the metric ̺ defined above in the standard terminology of electrical networks as in textbooks like [29,43]. In this context, we also highlight Kigami's work [38,39], which gives a treatment of Dirichlet forms on (metric) graphs centered around the resistance metric.
We start by introducing a quantity which can be related to the free effective resistance in the case of locally finite graphs with c ≡ 0 (see Proposition 3.21 below). Let (b, c) be a graph over X. Define r : Then, the function f /s is a candidate for g in the definition of r above. We estimate As ε > 0 is arbitrary we infer that Conversely, let ε > 0 and g ∈ D, |g(x)−g(y)| = 1, be a function such that 1/ Q(g) ≥ r(x, y) − ε ≥ 0. Then, the function g/ Q(g) 1 2 satisfies Q(g/ Q(g) 1 2 ) = 1, and, so, it is a candidate for f in the definition of ̺(x, y). This means that Combining these inequalities we obtain r = ̺ 2 as claimed.
Remark. As discussed in the first remark of Subsection 3.1, the supremun in the definition of ̺(x, y) can be replaced by a maximum. Using this in the above proof, we can easily infer that the supremum can also be replaced by a maximum in the definition of r.
We next sketch the connection to the free effective resistance metric. For a graph (b, 0) over a finite set X, the map r is called effective resistance. It is shown in [38, Theorem 2.1.14] and [29,Lemma 4.5] that r is a metric and, thus, it is called the effective resistance metric in this case.
This definition is, in fact, just one of the many well-known equivalent definitions of effective resistance. The physical intuition behind this is that the electrical potential on X induced by an external voltage source applied to x and y is the energy minimizer among all functions with the given boundary conditions; recall the formula E = V 2 /R eff from elementary physics, expressing the energy E in terms of the imposed voltage V and effective resistance R eff .
When X is infinite, there are at least two standard notions of effective resistance; the one most relevant to this paper, which coincides with r described above, is the free effective resistance defined as follows.
Given a finite subset X ′ of X, we think of the restriction b ′ of b to X ′ as a weighted graph and call it the subgraph induced by X ′ . If (b, 0) is additionally locally finite, we define the free effective resistance between x and y as the infimum over the effective resistances between x and y for all finite subgraphs containing x and y. We denote this quantity by r free (x, y).
In this way, r free is defined via an approximation procedure by finite graphs. It turns out that it can, in fact, be expressed by virtually the same term as r in the case of finite graphs above. This is well-known. For example [ holds. Moreover, the map r is a metric on X.
Remark. The proofs of the previous proposition presented in the literature do not seem to cover a non-locally finite setting. However, for our applications in Section 8, this is no restriction as we consider only locally finite examples there.

Topology: Canonically compactifiable graphs
Let X be a countable set, m a measure on X, and (b, c) a weighted graph over (X, m). We give a characterization of when X is relatively compact in a natural way. This will be used in order to define a boundary ∂X of X. Our considerations are based on C * -algebra techniques.

Basic definition and features.
In this subsection, we study the topology of a graph by assigning a natural C * -algebra to it. In order to do so, we need D to be an algebra of bounded functions.
Remark. Let us point out that both b and c can play a role in making a graph canonically compactifiable. In fact, it is not hard to construct examples of graphs (b, c) such that (b, 0) is not canonically compactifiable but (b, c) is. To construct such an example, it suffices to consider X = N with b(n, n ′ ) = 0 for |n − n ′ | = 1 and b(n, n + 1) = 1 and c(n) −→ ∞ as n −→ ∞. Then, (b, c) obviously is canonically compactifiable. However, the function is unbounded and has finite energy on (b, 0).
The following lemma shows that the embedding D ⊆ ℓ ∞ (X) is actually continuous.
If we show that g ≡ 0, then the statement follows from the closed graph theorem. Since, by Lemma 3.6, point evaluation is continuous whenever b is connected, we have that j(f n )(x) = f n (x) −→ 0 for all x ∈ X. As j(f n ) −→ g with respect to · ∞ we infer g ≡ 0.
We next give a characterization as well as sufficient conditions for compactifiability in terms of the metrics ̺ and d and the intrinsic metrics introduced in the previous section.
Recall that diam σ (X) := sup x,y∈X σ(x, y) denotes the diameter of X with respect to any (pseudo)metric σ. Theorem 4.3. Let (b, c) be a connected graph over X. Then the following assertions are equivalent: If c ≡ 0, this is furthermore equivalent to the following assertion: (iv) diam σ (X) < ∞ for any pseudometric σ intrinsic with respect to a finite measure m on X.
(iv)=⇒(i): Let f ∈ D be arbitrary. Then, σ := σ f is an intrinsic pseudometric with respect to a finite measure by Proposition 3.10. Fix now an arbitrary o ∈ X. Then, holds for any x ∈ X. As diam σ (X) is finite by (iii), we infer that f is bounded.
Remark. Due to Theorem 3.14, condition (iv) in the previous Theorem is equivalent to the (a priori stronger) condition: (iv') There exists a β ≥ 0 such that diam σ (X) ≤ β for every metric σ which is intrinsic with respect to a measure m with m(X) ≤ 1.
The following corollaries give sufficient condition for compactifiability via conditions on the metric d introduced in Section 3.1 and the intrinsic metrics. Let us mention that, in general, the converse of Corollary 4.4 does not hold, see Example 8.8 in Section 8.
Proof. We have ̺ 2 ≤ d by Lemma 3.4. Therefore, the statement follows from the previous theorem.
Corollary 4.5. Let (b, c) be a connected graph over X with c ≡ 0 such that X σ is compact for any pseudometric σ which is intrinsic with respect to a finite measure. Then X is canonically compactifiable.
Proof. Compactness of X σ obviously implies finiteness of the diameter.
Thus, the corollary follows from the previous theorem.
We next give two classes of examples of graphs where the assumptions of Corollary 4.4 are clearly satisfied.
Clearly, in this case, diam d (X) < ∞ and (b, c) is canonically compactifiable by Corollary 4.4 (in Subection 4.6 we will have a closer look at this case).
The condition of summability of 1/b is by no means necessary in order to obtain a canonically compactifiable graph. This can easily be seen by considering trees. A first glimpse at this class of examples will be given next. A further study of this class will be undertaken in Section 8.
Example 4.7. Let (b, c) be a tree, i.e., a connected graph without cycles. Then, between any two points, there exists a unique path and the length of this path defines the value of the metric d between the points. Fix now an arbitrary vertex o ∈ X. Then, diam d (X) < ∞ holds if and only if there is a C > 0 such that for every natural number n and any path γ = (γ 0 , . . . , γ n ) starting at o we have n In particular, every such path is bounded.

4.2.
The compactification K. Any graph which is canonically compactifiable comes naturally with a canonical compactification K. This is discussed in this subsection. In the next subsection, we will see that this compactification K actually agrees with the Royden compactification (Theorem 4.11).
We start with a lemma which is certainly well-known.  If (b, c) is canonically compactifiable, then D is an algebra and A := Closure of D with respect to · ∞ is a commutative C * -algebra.
Proof. Notice that for f, g ∈ D ∩ ℓ ∞ (X) . It follows that D ∩ ℓ ∞ (X) is an algebra and, by assumption, D = D ∩ ℓ ∞ (X). Clearly, with complex conjugation as involution, D is a commutative involutive algebra that satisfies |f | 2 Hence, the closure of D with respect to · ∞ is a C * algebra.
Remark. Under the additional assumption that c ≡ 0, it is shown in [48] that the space of bounded functions in D with the norm Q(·) For a canonically compactifiable graph (b, c) over X we define A + := smallest C * -algebra containing 1 and A.
Then, A + is a commutative unital C * -algebra. It will be the key object in our subsequent study in this subsection.
Note that it can occur that A already contains 1. In this case, A is unital and agrees with A + . This case can be characterized as follows: Proposition 4.9. Assume that (b, c) is canonically compactifiable. Then, the following assertions are equivalent: Proof. Clearly (iii)=⇒(ii)=⇒(i). Assuming (i), we conclude that there are f n ∈ D such that f n −→ 1 in ℓ ∞ (X). Hence, there is an N such that |f N (x)| ≥ 1/2 for all x ∈ X. Since f N ∈ D, we have that (b) The proposition gives one reason for the relevance of graphs (b, c) with summable c.
Whenever (b, c) is a canonically compactifiable graph over X, we denote the set of characters of A + by K and the set of characters of A by K ′ . (Here, the characters are the non-trivial, linear multiplicative maps from the C * -algebra to the complex numbers.) Of course, By the commutative Gelfand Naimark theorem, K ′ is a locally compact Hausdorff space and A is isometrically isomorphic to C 0 (K ′ ) (where C 0 (K ′ ) is the space of continuous functions vanishing at infinity on K ′ which is understood to agree with C(K ′ ) if K ′ is compact). More precisely, the situation is as follows: The set K is compact with respect to the weak-*-topology and there is an isometric isomorphism, known as the Gelfand map, Moreover, if 1 ∈ D, then K ′ is not compact and K is its one-point compactification. In fact, in this case, the compact K satisfies In this case, the Gelfand map induces an isometric isomorphism With slight abuse of notation, we will denote the supremum norm on both A and C(K) with · ∞ .
The next theorem shows that K is a compactification of X in the usual sense. Proof. Clearly, δ x for x ∈ X, is a character of A + and, thus, j indeed maps X to K (and even to K ′ ). We will show denseness of j(X) in K as well as openness of the sets {j(x)} for any x ∈ X.
We restrict to the case that 1 does not belong to D. The other case is simpler and can be treated similarly.
We first show that X is dense in K. Choose k ∈ K, k = γ ∞ , arbitrarily and let W ⊆ K be an open neighborhood of k. We show that there is an x ∈ X such that j(x) ∈ W . By Urysohn's lemma, there is a function ϕ ∈ C(K) with ϕ(k) = 1, ϕ ≡ 0 on K \ W and 0 ≤ ϕ ≤ 1.
Hence, we have shown that for every k ∈ K and every neighborhood of k there exists x ∈ X such that j(x) is in this neighborhood. Therefore, j(X) is dense in K.
We Consider now an arbitrary γ = δ x . Since j(X) is dense in K, there exist δ yn with y n ∈ X such that δ yn −→ γ, n −→ ∞. As γ = δ x we can furthermore assume without loss of generality that δ yn = δ x for all n. Remark. Consider a canonically compactifiable graph (b, 0) over X. Then, it is not hard to see that the associated algebra A = A + does not change if (b, 0) is replaced by (b, c) with summable c. Thus, K, the character space of this algebra, also does not change. In this sense the compactification K is stable under the addition of a summable c. This is not surprising since, as observed in Section 2.1 and further described in Appendix A, the role of c can be simulated by one imaginary vertex at infinity and this vertex will not change the compactification.
The previous theorem shows that we can view X as an open subset of K. With slight abuse of notation we will not distinguish between X and j(X) to view X as a subset of K.

4.3.
K is the Royden compactification R. It turns out that the compactification we have constructed in the previous subsection agrees with the well-known Royden compactification R. This is shown in this subsection. In order to be more specific, we first must clarify the role of the killing term c in our considerations. The Royden compactification is commonly only considered in the case c ≡ 0, i.e., for graphs of the form (b, 0) over X. However, it turns out that the standard construction of this compactification as given, e.g., in [48] can be extended to arbitrary graphs (b, c). For the convenience of the reader, we discuss the details of the corresponding construction in Appendix B. The outcome of this construction is what we call the Royden compactification in this section. It is this compactification that we show to be equal to K.
Theorem 4.11. Let (b, c) be canonically compactifiable. Then K is homeomorphic to the Royden compactification R.
Proof. We will use the considerations of Appendix B. Note that the algebra B considered there agrees with D as our graph is canonically compactifiable. By Theorem B.3, there is then a unique (up to homeomorphism) locally compact Hausdorff space Y such that the following holds: (1) The set X is a dense open subset of Y .
(2) Any function in D can be extended to an element of C 0 (Y ).
(3) The algebra D separates points of Y .
(4) The algebra D does not vanish on any point of Y . We will show that the space K ′ of characters of A satisfies these properties. This will then imply the statement (as, in the case 1 ∈ D, we have K = K ′ = Y = R and, in the case 1 / ∈ D, we have that K is the one-point compactification of K ′ and R is the one-point compactification of Y .) Property (1) is immediate from Theorem 4.10.
To show property (2), notice that any element of D belongs to the algebra A. The algebra A, in turn, is isometrically isomorphic to C 0 (K ′ ) as discussed in the previous section. (Here, we use that C 0 (K ′ ) = C(K ′ ) if K ′ is compact.) Similarly, property (3) follows: By the definition of K ′ , the elements of A trivially separate the points of K ′ . Now, by the construction of A, we have that D is dense in A and hence the elements of D separate the points of K ′ as well. Finally, property (4) follows as, by the very definition of K ′ as non-trivial characters, the algebra A cannot vanish identically on any element of K ′ .
Let us stop for a moment and give a discussion of the relationship between our approach leading to K and earlier work along related lines concerning R: The idea of embedding a graph in a compact space via Gelfand theory is not new. It can already be found in the work of Yamasaki [57] and Kayano and Yamasaki [31]. A thorough discussion is then undertaken in Chapter VI of [48] (compare with Appendix B of the present paper). There, a graph (b, c) over X with c ≡ 0 is considered and it is shown that the space is a Banach algebra when equipped with the norm u Q,∞ := Q(u) 1/2 + u ∞ .
Note that this algebra always contains the constant functions (due to the assumption c ≡ 0). By the Gelfand theory, this Banach algebra gives rise to a compact space R and this space is called the Royden compactification in [48] after the work of Royden on Riemannian surfaces [46]. Now, our approach differs substantially from this approach in a number of ways. Most importantly, the main point of our work is to single out a class of graphs which can intrinsically be seen as relatively compact rather than to associate a compactification to any graph. Also, on a technical level, two differences are worth pointing out. One difference is that we work with C * -algebras rather than Banach algebras. This involves taking an additional limit when going from D to A. This limit will be of crucial importance in our treatment of the Dirichlet Problem later on. In fact, it is exactly this further limit that will allow us to solve it in a rather general context. The other difference is that we are not restricted to the case c ≡ 0. This is relevant as our perspective is to deal with arbitrary regular Dirichlet forms on discrete spaces (and these Dirichlet forms are in one-to-one correspondence with graphs (b, c) with arbitrary c ≥ 0). In fact, in order to state the previous theorem, we even had to extend the common definition of Royden compactification to the framework of general graphs (b, c) over X.
Given these differences between our approach to K and the construction of the Royden compactification, the statement of the preceding theorem seems rather remarkable in that it shows that one still obtains the same compactification.
To underline this last point we now include an example showing that, in general, D is strictly smaller than A in the case of canonically compactifiable graphs. is not of finite energy and, hence, does not belong to D. However, for any k ∈ N, the function f k (n) = 1 n 1+1/k , n ≥ 1, is of finite energy (as follows by estimating (f k (n + 1) − f k (n)) by the mean value inequality). Moreover, (f k ) converges to f with respect to the supremum norm and, hence, f belongs to A.

The Royden boundary.
In this subsection, we consider a canonically compactifiable graph (b, c) over X. According to the considerations of the previous subsections, there arises a canonical compactification K of X and this compactification agrees with the Royden compactification R. Here, we are concerned with the arising boundary We first note that points in the boundary are exactly the accumulation points of X: Proof. We will use the fact that K = R proved above. For the forward direction, note that every singleton set {x} is open in K for x ∈ X. For the other direction, we know, by Theorem 4.10, that X is dense in K. This implies that, for every k ∈ ∂X and every neighborhood W of k, there is an x ∈ X with x ∈ W . This implies that k is not a discrete point.
We now characterize the elements of D yielding functions which vanish on the boundary. Recall that D o is the closure of C c (X) in D with respect to · o according to Definition 3.2. Proof. We first show the inclusion "⊆": We start by proving that v| ∂X = 0 for all v ∈ C c (X). By Theorem 4.10 and Lemma 4.13 for every k ∈ ∂X there exists (x n ) in X with x n −→ k, n −→ ∞. Since (x n ) eventually leaves every finite set, we infer that v(x n ) = 0 for n sufficiently large for all v ∈ C c (X). Hence, v| ∂X = 0 for all v ∈ C c (X). Now, let u ∈ D o and let (v n ) in C c (X) be converging to u with respect to · o and, thus, by Lemma 4.2, with respect to · ∞ . This implies that v n − u ∞ −→ 0, n −→ ∞, and, in particular, u| ∂X = 0.
We now turn to the opposite inclusion "⊇": Let u ∈ D with u| ∂X = 0 be given. Without loss of generality, we can assume that u ≥ 0. Now, for ε > 0, consider the map with C ε (x) = 0 for x ≤ ε and C ε (x) = x − ε for x ≥ ε. It is not hard to see C ε u belongs to D as well (as C ε (p) ≤ p and |C ε (p) − C ε (q)| ≤ |p − q| for all p, q ∈ R).
Claim: C ε u has finite support. Assume the contrary. Then, there exists a sequence (x n ) in X of pairwise different points with u(x n ) ≥ ε. By the compactness of R, we can assume, without loss of generality, that (x n ) converges to some k. By Lemma 4.13, this k must belong to the boundary ∂X. On the other hand, by u(x n ) ≥ ε we have u(k) ≥ ε. This is a contradiction to the vanishing of u on the boundary. This proves the claim.
Claim: C ε u −→ u with respect to · o . It is not hard to see that C ε u converges pointwise to u. Moreover, a short calculation gives Combining this with the pointwise convergence, we infer from the Lebesgue dominated convergence theorem that This proves the claim.
With the preceding two claims the proof of the theorem is finished.
We finish this section be discussing a slight generalization of · o . Assume that (b, c) is canonically compactifiable. Let k ∈ R. Define f, g k = Q(f, g) + f (k) g(k), f, g ∈ D and f k := f, f 1 2 k . We call ( D, ·, · k ), k ∈ K, the generalized Yamasaki space.
Theorem 4.15. If (b, c) is canonically compactifiable and connected, then · k and · o are equivalent for all o, k ∈ R. In particular, ( D, ·, · k ) is a Hilbert space for all k ∈ R.
Proof. We will use that K agrees with R. It suffices to prove the statement for o ∈ X and k ∈ K. Let (k n ) be a net in X converging to k. Observe that Since, by Theorem 4.3, diam ̺ (X) < ∞ we conclude the equivalence of the norms. Since, by Proposition 3.7, ( D, ·, · o ) is a Hilbert space for all o ∈ X, we conclude the 'in particular'.

4.5.
Relationship between R and metric completions of X. In this subsection, we study how R is related to the metric completions studied in the preceding subsections.  Let (b, c) be canonically compactifiable and connected and X ̺ be the metric completion of X with respect to ̺. Then, there exists a unique continuous map κ : X ̺ −→ R extending the identity The map κ is one-to-one. If X ̺ is compact, it is a homeomorphism.
Proof. We will show a series of claims. Claim: Such a κ is unique. By denseness of X in X ̺ , uniqueness of such a map κ is clear. Claim: There exists such a κ: We will make use of the fact that R coincides with K (Theorem 4.11). We start with a slight reformulation of the Gelfand theory already discussed above: Let K be the set of all multiplicative linear maps from A to C. Then, K consists of the set of characters, i.e., non-vanishing multiplicative functionals K 0 together with the zero multiplicative functional 0 M . If 1 ∈ A, then K 0 is compact and is A is canonically isometrically isomorphic to C(K 0 ). If 1 does not belong to A, then K 0 is not compact, but K is and A is then canonically isometrically isomorphic to the algebra of continuous functions on K vanishing at 0 M . In this case, K is homeomorphic to K via the unique map which is the identity on K 0 and maps γ ∞ to 0 M .
To show existence of the desired map κ, it therefore suffices to provide a continuous map from X ̺ to K extending the identity such that 0 M is not in its range if 1 belongs to A. By definition of ̺, every function f ∈ D is Lipschitz continuous with respect to ̺ with constant Q(f ) 1 2 . Hence, it can be uniquely extended to a continuous function on X ̺ . The same is then true for any function f ∈ A (as A is the closure of D with respect to the supremum norm). Denote the extension of such a function f ∈ A to X ̺ by f . Then, clearly every k ∈ X ̺ defines a unique multiplicative linear functional . This shows that κ(k) is either 0 M or an element of K 0 and hence belongs to K. Moreover, if 1 belongs to A, then κ(k) can not agree with 0 M as it obviously takes the value 1 on the constant function 1. Moreover, it is not hard to see that κ is continuous since whenever (k n ) converges to k (w.r.t. ̺), then κ(k n )(f ) will converge to κ(k)(f ) for every f ∈ A. In fact, this is just continuity of the functions f . This gives existence of the desired map κ. Claim: The map κ is one-to-one: Let p, q ∈ X ̺ be given with p = q.
Then, ̺(p, q) > 0 holds. By the definition of ̺, there then exists f ∈ D with Q(f ) ≤ 1 and This immediately implies that κ(p) and κ(q) are not equal (as they take different values on f ). Claim: The map κ is a homeomorphism if X ̺ is compact: We have already seen continuity and injectivity. It remains to show that κ is onto and that the inverse is continuous. By compactness of X ̺ , it suffices to show that κ has dense range. This, however, is clear as X lies in the range of κ. It remains to show the statement on the functions f . By the continuity of κ and the definition of f , the function f • κ is continuous on X ̺ . By a short calculation, it can be seen to agree with f on X.
Hence, it must be equal to the (unique) extension of X to X ̺ . This proves the remaining statement of the lemma.
Remark. In general, (b, c) being canonically compactifiable does not imply that X ̺ is compact, as can be seen from Theorem 4.23 together with Example 8.6. More precisely, the mentioned theorem shows that (C) implies canonical compactifiability, that is (D), whereas the example shows that (C) does not imply the compactness of X ̺ , which is (B).
As a consequence of the previous theorem, we note the following. Proof. Uniqueness is clear from denseness of X in X d . Existence follows from the previous lemma and Theorem 3.5.
In the case of intrinsic metrics, we can say more.
Theorem 4.18. Let (b, c) be canonically compactifiable and connected with C := x∈X c(x) < ∞. Let m be a measure on X with m(X) < ∞ and σ be an intrinsic metric with respect to m such that X σ is compact.
Then, there exists a unique continuous map λ = λ σ : R −→ X σ extending the identity on X and this map is onto.
Proof. Again, using Theorem 4.11, we can work with K instead of R.
Uniqueness of λ is clear. By the usual denseness argument surjetivity of λ is clear from compactness of R and continuity of λ. Thus, it remains to show existence. Consider the set C Lip (X σ ) of Lipschitz functions with respect to σ. By compactness of X σ , any such function is bounded. Moreover, whenever f belongs to C Lip (X σ ) there exists a constant L with |f (x) − f (y)| ≤ Lσ(x, y) and hence f satisfies This shows that C Lip (X σ ) can be seen as a subset of D and hence a subalgebra of A. Thus, we have a natural isometric homomorphism where f | X denotes the restriction to X. Now, the constant function obviously belongs to C Lip (X σ ). Moreover, C Lip (X σ ) clearly separates points of X σ as it contains σ(x, ·) for any x ∈ X. Hence, by the Stone-Weierstrass Theorem, the algebra C Lip (X σ ) is dense in C(X σ ). As j is isometric, it can therefore be extended to an isometric map (again denoted by j) j : C(X σ ) −→ A = C(K).
By standard results from Gelfand theory, this map j now induces a continuous map j * : K −→ X σ with f (j * (k)) = k(j(f )). Then, λ = j * is the desired map.

4.6.
A key example: If 1/b and c are summable. The results of the previous subsections have given relationships between the various metric completions of a graph (b, c) over X. As the counterexamples in the last section show, these completions will be different in general.
In this subsection, we study a particular class of examples in which essentially 'all' completions agree. More precisely, we consider connected graphs (b, c) over X with In this case, we can make a thorough study of compactness properties of X d and X ̺ .
Whenever (b, c) is a connected graph over X satisfying B < ∞, there is a canonical finite measure M on X with total mass B defined by .
Note that M vanishes nowhere due to connectedness. Now, there are some crucial consequences to B < ∞: One consequence is that d is an intrinsic metric with respect to a finite measure, namely, M. Another most important consequence is that X is totally bounded with respect to d. This is the content of the next proposition.  Let (b, c) be a connected graph over X. Assume B < ∞ and let M be the associated measure. Then, the following hold.
(a) The space X d is compact and so is X ̺ .
(b) The metric d is an intrinsic metric with respect to M.
Proof. (a) To show the compactness of X d , it suffices to show that, for any ε > 0, the space X can be covered by finitely many ε-balls (w.r.t. d). This follows easily from B < ∞. By Theorem 3.5, the map ι is continuous and onto and X ̺ is then compact as well.
(b) Note that d(x, y) ≤ 1 b(x,y) whenever x and y are neighbors. Then, a direct calculation gives This finishes the proof.
Remarks. (a) Let us note that if B < ∞ and c ≡ 0 hold, then the metric d is -in a certain sense -the maximal metric which is intrinsic with respect to a finite measure. More precisely, whenever σ is an intrinsic metric with respect to a measure m with total mass m(X), then σ ≤ m(X)̺ by Theorem 3.14. Moreover, by Lemma 3.4, we have ̺ 2 ≤ d. Putting this together, we infer σ ≤ m(X)d 1/2 .
(b) A further discussion of X d in the situation B < ∞ is given below in Corollary 4.22.
From this proposition we immediately infer the first main result of this section.  b(x,y) < ∞. Then, the unique continuous map ι : X d −→ X ̺ extending the identity on X is a homeomorphism. In particular, all three spaces X d , X ̺ and R are compact and homeomorphic via the unique continuous maps extending the identity on X.
Proof. By Proposition 4.19, the metric d is an intrinsic metric with compact X d . Hence, Theorem 4.18 gives a unique continuous map λ : R −→ X d extending the identity on X and this map is onto.
By Theorem 4.16, we furthermore have a unique continuous map κ : X ̺ −→ R extending the identity on X and this map is onto as well.
Finally, by Theorem 3.5, there is a unique map ι : X d −→ X ̺ extending the identity on X and this map is onto as well. Thus, we end up with the following diagram of maps each map being onto and the unique continuous extension of the identity on X. This gives that their composition λ•κ•ι must be the identity and all maps must be one-to-one. Thus, they are all bijective and hence homeomorphisms (as the underlying spaces are compact).
It was proved in [15] that if B < ∞ is satisfied, then X d is canonically homeomorphic to a well-known space called the end-compactification or Freudenthal compactification of X. Combined with the last theorem and Theorem 4.11, this yields the following corollary. and R is homeomorphic to the end-compactification of X.
In particular, we obtain that the boundaries of X d , X ̺ , K and R are totally disconnected in this case.
Remark. Assume the situation of the previous theorem. Then, the d-diameter of X is finite. Thus, any metric σ which is intrinsic with respect to a finite measure is bounded by Corollary 3.18. By Theorem 3.13, there then exists, for any such metric σ, a unique continuous map γ : X ̺ −→ X σ and this map is onto.

4.7.
A little summary. We summarize a large part of the preceding considerations in the following result. Moreover, the following statements hold: • (A) implies the existence and uniqueness of a continuous surjective map ι : X d −→ X ̺ extending the identity on X.
• (B) implies the existence and uniqueness of a homeomorphism κ : X ̺ −→ R extending the identity on X.
• If c ≡ 0, then (B) implies existence and uniqueness of a continuous surjective map γ : X ̺ −→ X σ for any metric σ which is intrinsic with respect to a finite measure. • If c ≡ 0, then (C) implies existence and uniqueness of a continuous surjective map λ : R −→ X σ for any metric σ which is intrinsic with respect to a finite measure.
Proof. We first deal with the two chains of implications.
We now turn to the proofs of the four last statements: The first statement follows from Theorem 3.5. The second statement follows from Theorem 4.16. The third statement follows from Theorem 3.13. The forth statement follows from Theorem 4.18.

Operator theory: Discrete spectrum and Dirichlet problem
In this section, we use the canonical compactification discussed above to study operator theory. We will show that the corresponding operators have discrete spectrum and that the Dirichlet Problem has a unique solution. Moreover, we will explicitly describe the domain of the Dirichlet Laplacian. 5.1. Discrete spectrum. In this subsection, we give criteria for an operator on a graph of finite measure to have compact resolvent. In this case, the spectrum of the operator is purely discrete.
Proof. We only consider the semigroup operators e −tL , t > 0. The statements on resolvents can then be derived by standard techniques.
Let t > 0 be arbitrary. We have Since e −tL is a continuous operator on ℓ 2 (X, m) we now obtain, by a simple application of the closed graph theorem, that e −tL can be seen as a continuous map from ℓ 2 (X, m) to ℓ ∞ (X). This shows the first statement. If m(X) < ∞, there is a canonical continuous embedding Then, e −tL = je −tL is a composition of a continuous maps from ℓ 2 (X, m) to ℓ ∞ (X) with a continuous map from ℓ ∞ (X) to ℓ 2 (X, m). Thus, it is a Hilbert-Schmidt operator by factorization principle (or a direct calculation). Then, is trace class as a product of two Hilbert-Schmidt operators.
Corollary 5.2. Let (b, c) be canonically compactifiable, connected and m(X) < ∞. If L is the operator associated to a closed, symmetric form Q with Q (D) ⊆ Q ⊆ Q (N ) , then the spectrum of L is purely discrete.
Proof. This follows directly from Theorem 5.1 and the spectral mapping theorem.
Remarks. (a) If the form Q in the previous corollary is additionally assumed to be a Dirichlet form, then Theorem 2.1.4 and Theorem 2.1.5 of [8] give that • e −tL , t > 0, and (L + α) −1 , α > 0, are norm analytic and compact on all ℓ p (X, m), 1 ≤ p ≤ ∞, • the spectra of the generators of e −tL on ℓ p (X, m) agree for all 1 ≤ p ≤ ∞. (b) There has been quite some recent interest in graphs whose Laplacians have purely discrete spectrum, see, e.g., [17,32,35,37].
A general discussion of various equivalent characterizations of purely discrete spectrum in the context of perturbations by potentials for arbitrary selfadjoint operators in a measure space can be found in [41].
Here, we point out the following alternative formulation (and proof) of the previous corollary. Proof. Clearly, · Q is a restriction of the norm · Q on D. Let (f n ) be a sequence in D which is uniformly bounded with respect to · Q and thus, by Lemma 5.4, with respect to · o . As (b, c) is canonically compactifiable, Lemma 4.2 then shows that the sequence (f n ) is uniformly bounded with respect to the supremum norm. Thus, it contains a pointwise converging subsequence. By m(X) < ∞, this sequence must then converge in ℓ 2 (X, m). This proves the theorem.
We end this subsection with a general lemma, which will also be used in the characterization of the Dirichlet Laplacian (Theorem 5.9).
Lemma 5.4. Let (b, c) be a canonically compactifiable graph over X equipped with a measure m with m(X) < ∞. Then, · Q and · o are equivalent norms on D.
Proof. Obviously, On the other hand, by Lemma 4.2 and m(X) < ∞, there exists a C > 0 with Hence, 5.2. The Dirichlet problem. In this subsection, we consider the boundary value problem Lu = 0 on X u| ∂X = ϕ on a canonically compactifiable graph (b, c) over X. Note that there is no measure involved in our discussion. For somewhat similar considerations in the context of metric graphs we refer the reader to [4]. Complementary results on when there are no (bounded) harmonic functions can be found [24].
Whenever we have a canonically compactifiable graph (b, c) over X, we denote the set of continuous functions on its boundary by C(∂X). Moreover, we set C 0 (∂X) := C(∂X) if x∈X c(x) < ∞ and C 0 (∂X) = {ϕ ∈ C(∂X) : γ ∞ (ϕ) = 0}, otherwise. Then, the main result of this subsection reads as follows.
Theorem 5.5. (Uniqueness and existence of solutions to the DP) Let (b, c) be a canonically compactifiable graph over X. Then, the equation has a unique solution u ∈ A for all ϕ ∈ C 0 (∂X).
Remark. Carlson [5,Theorem 4.5] proved that the Dirichlet problem for continuous functions on the boundary of X d is solvable when (A) and a further strong condition hold. In comparison, Theorem 5.5 assumes only the much weaker (D) but the boundary on which the Dirichlet problem is solved is, in general, smaller. Note that, assuming (A), solvability of the Dirichlet problem on the boundary of X d implies solvability on ∂X, since by the first two statements of the second part of Theorem 4.23 there is a a continuous surjection from X d to R extending the identity on X. It would be interesting to know whether the Dirichlet problem on the boundary of X d is solvable for every graph satisfying (D); this issue is further discussed in the last section.
The proof of Theorem 5.5 will be given at the end of this subsection after some preliminary considerations. In particular, for the proof of the theorem we need a maximum principle which states that every harmonic function takes its maxima and minima on the boundary. As this may be of independent interest, we present a slightly more general discussion.
We start with two statements on subharmonic functions, i.e., functions satisfying Lf ≤ 0.
Proposition 5.6. Assume that (b, c) is connected. If f ∈ F is nonnegative and not constant and satisfies Lf ≤ 0 on X, then f does not attain a maximum on X.
Proof. Let f be as in the statement. Assume that f attains its maximum on X at k ∈ X. By Lf ≤ 0, we then have By maximality of f (k) and non-negativity of f we infer f (x) = f (k) for all neighbors x of k. Continuing this argument and using connectedness, we infer that f is constant (and equal to f (k)) and this is a contradiction.
Proof. This follows by a direct computation: Lf = 0 implies αLf = 0 for all complex numbers α. Thus, for any k ∈ X and complex number α, we obtain Choosing α with |α| = 1 and αf (k) = |f (k)|, we infer and the desired statement follows easily.
Proof. As f belongs to A, the function |f | attains its maximum on K.
Combining the previous lemma and the preceding proposition, we infer that |f | attains its maximum on ∂X. This directly gives the statement of the corollary.
Proof of Theorem 5.5. We only consider the case where x∈X c(x) < ∞. The other case can be treated similarly. We have to show existence and uniqueness of solutions.
Uniqueness of solutions. Uniqueness is a direct consequence of Corollary 5.8.
Existence of solutions. Consider the set G ⊆ C(∂X) of functions ϕ such that there exists f ∈ D with ϕ = f | ∂X .
Step 1. For all ϕ ∈ G there is a unique solution of the boundary value problem.
Proof of Step 1. Fix k ∈ ∂X with k = γ ∞ . Recall that ·, · k is an inner product on D making it into a Hilbert space by Theorem 4.15. Let ϕ ∈ G. Consider C := {w ∈ D : w| ∂X = ϕ}.
Then, C is clearly convex. Moreover, it is closed with respect to · k by Theorem 3.7 and Lemma 4.2.
By standard Hilbert space theory, see, e.g., [52], there exists then a minimizer u of · k on C. Hence, since v| ∂X ≡ 0 for all v ∈ C c (X) by Theorem 4.14, we get all v ∈ C c (X) and all t ∈ R. Therefore, the real part of Q(u, v) is 0 for all v ∈ C c (X) and repeating the argument with it in place of t, gives that Q(u, v) = 0 for all v ∈ C c (X). By the discussion on integration by parts in Section 2.3 we have D ⊆ F as well as Q(u, v) = Step 2. Suppose that (f n ) in D solves Lf n = 0, f n | ∂X = ϕ n , for some (ϕ n ) in C(∂X). Suppose, furthermore, that ϕ n −→ ϕ uniformly as n −→ ∞. Then, (f n ) converges uniformly to some f ∈ A that solves Lf = 0, f | ∂X = ϕ.
Proof of Step 2. By the maximum principle, Corollary 5.8, which implies the uniform convergence of f n to some f ∈ ℓ ∞ (X). By the definition of A, we have f ∈ A. Since f n −→ f in ℓ ∞ (X) we conclude that Lf n −→ Lf by Lebesgue's theorem of dominated convergence. This finishes the proof of Step 2.
We can now conclude the existence proof as follows: By construction, the algebra D is dense in A. In particular, D separates points of K. Hence, G separates points of ∂X. Moreover, by Proposition 4.9, the algebra G does not vanish identically on any point of ∂X. Now, the Stone-Weierstrass theorem gives that G is dense in C(∂X). The statement of the theorem then follows by combining Step 1 and Step 2.
5.3. The Laplacian with Dirichlet boundary conditions. In this subsection, we give an explicit description of the domain of the form Q (D) and of the domain of the associated Laplacian in the case of canonically compactifiable graphs over discrete finite measure spaces. We will show that functions in the domain are exactly those vanishing on the boundary and use this to give an explicit description of the Laplacian as well.
Let (b, c) be a graph over (X, m). Recall that the form Q (D) has the domain Proof. We first show the statement on the form domain. Clearly, · Q is a restriction of the norm · Q on D. By Theorem 4.14 and the definition of D o , it then suffices to show that the norms · o and · Q are equivalent on D. But this is precisely the statement of Lemma 5.4.
As for the last statement of the theorem, we note that L (D) is a restriction of L and that D is contained in F by the discussion of Subection 2.3. Now, the statement follows from from the definition of L (D) and the formulas for 'integration by parts' discussed in Subection 2.3.
6. Geometry: The eigenvalue 0 and heat kernel convergence In this section, we first present an analogue of a result of Yau [58] on manifolds characterizing the situation of finite measure and then present an application of an analogue to a theorem of Li.
We start with a spectral characterization of the finiteness of m(X) when c ≡ 0. Proof. This is true for any non-negative form Q by the spectral theorem. Proof. This is clear. Given these three facts, the theorem follows easily. Proof. It suffices to consider the case when (b, c) is connected. It then suffices to show that E 0 = 0 cannot be an eigenvalue if c ≡ 0. However, this is clear.
Let Q satisfy Q (D) ⊆ Q ⊆ Q (N ) and let L be the corresponding self adjoint operator. Then, the heat semigroup e −tL defined by the spectral theorem has a kernel p : X × X × [0, ∞) −→ C, called the heat kernel, satisfying for all f ∈ ℓ 2 (X, m). By [20,Theorem 7.3] the heat kernel is positive on every connected component.
The following is a consequence of an analogue of a theorem of Li [42] for graphs (see [20,36] which give an analogue to a result of [6] from which the theorem of Li follows). for all x, y ∈ X. In particular, this holds for Q = Q (N ) .
Proof. By the assumptions and Theorem 6.1 of this section, we obtain 1 is a normalized positive eigenfunction of L. By an analogue of a theorem of Chavel and Karp for graphs (see [20,Theorem 8.1], [36,Corollary 5.6]) there exists a unique non-negative Φ on X such that for all x, y ∈ X. Here, Φ ≡ 0 if the E 0 is not an eigenvalue and Φ is the unique ℓ 2 -normalized positive eigenfunction to E 0 , otherwise. Hence, we have p t (x, y) −→ Φ(x)Φ(y) = 1 m(X) and the corollary follows. The 'in particular' follows, since we already know that 1 ∈ D(Q (N ) ).

Remarks. (a)
There are examples such that m(X) < ∞ and the form Q (N ) is bounded, i.e., satisfies Q (N ) (u, u) ≤ κ u 2 for some κ ≥ 0. More precisely, by [20,Theorem 9.3], this is exactly the case if there is C ≥ 0 such that y b(x, y) + c(x) ≤ Cm(x) for all x ∈ X. In this case Q (N ) = Q (D) . In particular, the previous corollaries then apply to Q (D) as well.

Probability: Recurrence and stochastic completeness
In this section, we discuss a characterization for recurrence. We assume that c ≡ 0 and let (b, 0) be a connected graph over (X, m).
The heat semigroup e −tL (D) , t ≥ 0, defined by the spectral theorem on ℓ 2 (X, m) can be extended by monotone limits to a semigroup on for some (all) t > 0, where 1 is the constant function 1 on X. Otherwise, we call Q (D) stochastically incomplete. In [20,Section 6] it was discussed that the definition of stochastic completeness only makes sense for the Dirichlet Laplacian L (D) . In general, it is known that recurrence implies stochastic completeness which implies that Q (D) = Q (N ) (see [13,Lemma 1.6.5] for the first implication and [20,Corollary 5.3] for the second one). We now discuss a result of [47] giving that, in the case of finite measure, these three properties are equivalent.  Proof. The implications (i)=⇒(ii)=⇒(iii) follow from the references above and do not require finiteness of the measure. The implication (iii)=⇒(i) can be shown as follows: Due to the finiteness of the measure, the constant function 1 belongs to D(Q (N ) ). By (iii) it then belongs to D(Q (D) ) as well. As D(Q (D) ) is the closure of C c (X) with respect to · Q (N) we obtain, in particular, that the constant function 1 can be approximated with respect to · o by functions with compact support. Given this, (i) follows from the characterization of recurrence given in Theorem (3.63) of [48] (after observing that recurrence of a continuous time random process is equivalent to the recurrence of that process restricted to jumps only in discrete time). In this subsection, we assume that b induces a tree, that is, b is connected and there exists no path (x 0 , . . . , x n ) with n ≥ 2 such that b(x n , x 0 ) > 0. Furthermore, we assume that c ≡ 0.
The proof of this lemma is rather immediate using the electrical network connection: In the context of electrical networks, it is a wellknown rule that, when connecting networks in series, effective resistances add up. Thus, one figures that the effective resistance r equals d on a finite tree. Now, using Proposition 3.21 and Theorem 3.20 we obtain the statement of the lemma. However, as we omitted the proof of Proposition 3.21, we give a slightly different proof for the sake of being self-contained.
Proof of Lemma 8.1. We know from Lemma 3.4 that ̺ 2 ≤ d, so we now only need to prove the converse direction. Let x, y ∈ X be arbitrary and let (x 0 , . . . , x n ) be a path with x 0 = x and x n = y. We construct a function f as follows: x j and x j+1 are neighbors in the path, and f (x) − f (y) = 0 if x and y are neighbors not on the path. Thus, .
As the path above is the unique path connecting x 0 and x n , the last quantity equals d(x 0 , x n ). As the function f has finite Q energy, we have, by the definition of ̺, that Moreover, we obviously have Combining this with the already shown Q(f ) = d(x 0 , x n ), we obtain from the previous inequality d 1/2 (x 0 , x n ) ≤ ̺(x 0 , x n ) and the proof is finished.
Lemma 8.1 immediately implies that the canonical map ι : X d −→ X ̺ is a homeomorphism and so we have the following corollary.  Proof. By Theorem 4.3, for a graph being canonically compactifiable is equivalent to diam X ̺ < ∞. By Lemma 8.1 this is equivalent to diam X d < ∞ in the case of trees. In particular, this implies that b(x, y) ≥ ε for some ε > 0 (if x n , y n ∈ X existed with b(x n , y n ) −→ 0, then diam X d ≥ d(x n , y n ) = 1/b(x n , y n ) −→ ∞ as n → ∞). Hence, b is locally finite by the assumption y∈X b(x, y) < ∞, x ∈ X.
Note that the corollary above does not hold in the general case: Example 8.4 ((D) =⇒ locally finite). Let (b, c) be a locally finite, canonically compactifiable graph over X. Pick a vertex x ∈ X and an infinite set of vertices y n ∈ X, n ≥ 0, such that b(x, y n ) = 0. Define the graph b ′ by setting b ′ (x, y n ) = b ′ (y n , x) > 0, n ≥ 0, such that n b ′ (x, y n ) < ∞ and b ′ (y, z) = b(y, z) for all other y, z ∈ X. The graph (b ′ , c) is not locally finite as x has infinitely many neighbors. Let In conclusion, (b ′ , c) is canonically compactifiable but not locally finite.  Next, we give an example of a tree which is totally bounded for each intrinsic pseudo metric with respect to a finite measure but it is not totally bounded for ̺. Example 8.6 ((C) =⇒ (B)). The example is an infinite comb with finite d diameter, i.e., it can be thought of as a one sided infinite ray with weights b increasing along the line (which gives it finite length) and from each vertex a copy of the same one sided infinite ray with finite length emanates.
Let X n = {x n,k | k ≥ 0}, n ≥ 0, be one sided infinite rays and X = n≥0 X n . We let the edge weight b on X n be given by b(x n,k−1 , x n,k ) = 2 k , for every k ≥ 1 Moreover, b(x n−1,0 , x n,0 ) = 2 n , for every n ≥ 1.
For all other pairs of vertices we let b be zero. Moreover, we let m ≡ 1 and c ≡ 0. We have diam X n d = 1 for n ≥ 0 and observe that X cannot be covered by finitely many d balls of radius 1. Thus, (A) is not satisfied. On the other hand, we have diam X d = 3 < ∞ and by We end this subsection with a lemma which shows that a (strengthening of the) converse of Corollary 3.16 is also true in the case of trees.
Lemma 8.7. Let (b, 0) be a tree over (X, m). If every intrinsic metric is bounded by Proof. Let x, y ∈ X with b(x, y) > 0. On a tree, a pseudometric d ℓ given by a length function ℓ satisfies So, let ℓ be such that ℓ(x, y) = ℓ(y, x) = ( b(x,y) m(x)∧m(y) ) − 1 2 and ℓ ≡ 0 on X × X \ {(x, y), (y, x)}. It can be directly checked that d ℓ is an intrinsic metric and, thus, bounded by a − 1 2 by assumption. Hence, assuming without loss of generality m(x) ≤ m(y) and using that d ℓ is an intrinsic metric, we arrive at The example can be thought of as a one sided infinite ray, where we put over each edge an increasing number of additional paths in the form of triangles. It turns out that d is not effected by these additional paths but ̺ is.
n } and let a symmetric b be given such that n , x n+1 ) = n, for n ≥ 1, 1 ≤ k ≤ n, and b takes the value zero otherwise. Let further assume that c ≡ 0 and m ≡ 1.
We will show that X ̺ \ X consists of one point and X is totally bounded with respect to ̺.
To show this, we can either calculate ̺(x 1 , x n ) ≤ 1/n 2 directly using basic calculus and Lagrange multipliers or we use the electrical network connection and calculate r(x n , x n+1 ), n ≥ 1, first. Note that the free effective resistance r(x n , x n+1 ) is smaller than or equal to the resistance between x n and x n+1 on the subgraph induced by {x n , x n+1 , x 1 , . . . , x (n) 1 }. This, however, can be computed either using the rules for networks connected in series and in parallel [43,Chapter 2.3] or by basic calculus to be 1/n 2 . Hence, r(x n , x n+1 ) ≤ 1/n 2 and by Theorem 3.20 and the triangle inequality for r Moreover, ̺ 2 ≤ d by Lemma 3.4 and, therefore, for all n ≥ 1 and 1 ≤ k ≤ n. Hence, diam (X ̺ ) < ∞, the ̺-boundary consists of one point and X is totally bounded with respect to ̺, that is, (B) is fulfilled.
On the other hand, as n → ∞ and, therefore, diam (X d ) = ∞. As additionally d(x 1 , x (k) n ) ≥ d(x 1 , x n ) for all n ≥ 1 and 1 ≤ k ≤ n, we conclude that X d = X.
Hence, (A) is not fulfilled, although (B) is.
By similar means we can also show that ι : X d −→ X ̺ from Theorem 3.5 is in general not an embedding (i.e., it is not injective).
Example 8.9 (ι is not injective). We can think of the graph as two one sided infinite rays (x Let n | n ≥ 0, 0 ≤ k ≤ n + 1} and let b be symmetric and satisfy n , x (j) n ) = 1, i = 0, 1, j = 0, . . . , n + 1, j = i. and let b be zero otherwise as well as c ≡ 0. One sees immediately that the d boundary of X consists of two distinct points x (0) , x (1) , which arise from the d Cauchy sequences (x n ) n≥0 and satisfy d( x (0) , x (1) ) = 1. Now, ι( x (0) ) and ι( x (1) ) belong to the ̺ boundary of X. However, one can compute as in the example above that ̺(x n ) → 0, n → ∞ and, therefore, ι( x (0) ) = ι( x (1) ) with respect to ̺. Thus, ι is not injective. 8.3. Problems and outlook. In this subsection, we discuss some open questions and problems raised by our considerations.
In the subsections above, we show that (C) =⇒ (B) =⇒ (A). In Corollary 8.5 we have (C) ⇐⇒ (D) for trees. This gives rise to the following question: On a different issue, it would be interesting to know whether the converse of Lemma 4.8 holds.
Problem 2. Does the fact that D is an algebra imply that (b, c) is canonically compactifiable?
To show this, one could try to present an unbounded f ∈ D such that f 2 ∈ D.
Corollary 5.2 tells us that being canonically compactifiable and having finite measure implies discrete spectrum, i.e., compact resolvent for the operator L arising from any Q (D) ⊆ Q ⊆ Q (N ) . It would be interesting whether some kind of converse holds (see also the remark after Corollary 5.2). We have shown that the Dirichlet problem can always be solved on the boundary of the Royden compactification R under condition (D) (Theorem 5.5). It is natural to ask whether it can also be solved on the (larger) boundary of X d . Here, we can point out the following: Example 8.9 shows that ι : X d −→ K is, in general, not an embedding (even if (A) holds). This means that the functions of finite energy (which define the set K) will not separate points of X d \ X. Thus, the Dirichlet problem with the d-boundary of X can, in general, not be solved with functions of finite energy (or uniform limits thereof). This does not preclude, however, the possibility that it can be solved within a larger class of functions (contained in the domain of the generalized Laplacian). This leads to the following problem. In Subsection 5.3, we showed that for canonically compactifiable graphs it becomes very clear why L (D) is called the Laplacian with Dirichlet boundary conditions. It seems to be essentially harder to even formulate a corresponding result for L (N ) , i.e., the Laplacian with Neumann boundary conditions. The reason is that one has to define the derivative on the boundary. Thus, we formulate the corresponding question rather vaguely.
Problem 5. What can be said about L (N ) and Q (N ) in view of Theorem 5.9?
Appendix A. Reducing summable c ≡ 0 to the case c ≡ 0 In this section, we discuss how we can reduce the case of nonzero summable c to the case c ≡ 0. The basic idea is to add a virtual vertex to X and extend functions from the domain of the form Q by zero at this vertex.
We assume here that X is an infinitely countable set and (b, c) is a weighted graph over X which is connected. Moreover, we assume that c is summable, i.e., x∈X c(x) < ∞.
Using this assumption, we add the element ♥ to X, i.e., set . By the assumption on c, this new graph satisfies the summability condition on the vertices. Consider the extended form defined for all functions f on X ♥ (and, possibly, taking the value ∞). Define its domain via D ♥ = {f ∈ C(X ♥ ) : Q ♥ (f ) < ∞}. Let L ♥ be the corresponding formal operator given by Remark. The restriction of F ♥ to X just gives F and for The next theorem shows that we can embed D into D ♥ . At the same time, it demonstrates the difference between these two spaces. Furthermore, with respect to the inner product f, g ♥ = Q ♥ (f, g) + f (♥)g(♥), we have the orthogonal decomposition where H ♥ is a one dimensional space of functions f which are harmonic on X, i.e., satisfy L ♥ f (x) = 0 for x ∈ X.
Proof. The identification is clear. Note that, with ♥ instead of o and Q ♥ instead of Q, we are exactly in the situation of Lemma 3.6. Now, by this lemma, convergence with respect to · ♥ implies pointwise convergence and the subspace D is closed. Thus, we have an orthogonal decomposition of D ♥ into D and its orthogonal complement, which we denote by H ♥ . We now show that this space is one dimensional: Let h 1 , h 2 ∈ H ♥ with h 1 (♥) = h 2 (♥) = 1 be given. Then h 1 − h 2 ∈ H ♥ and h 1 − h 2 ∈ D. Thus h 1 − h 2 ≡ 0 and we are done.
It remains to show that functions from H ♥ are harmonic in X. This follows from the definition of the orthogonal complement of D and an 'integration by parts' formula as found in Subsection 2.3 above, see [19,20] for details as well. Specifically, this formula gives for all f ∈ D ♥ and g ∈ C c (X ♥ ). Using this formula for f in the orthogonal complement of D with respect to ·, · ♥ and arbitrary g ∈ C c (X) (considered as elements in D ⊂ D ♥ ) we then obtain Here, we used g(♥) = 0 in the last two steps. As g ∈ C c (X) is arbitrary, this easily gives the desired statement.
Remark. The theorem asserts that any function in H ♥ is harmonic in X. If the graph (b ♥ , 0) on X ♥ is recurrent, we can also prove a converse: In that case, D ♥ is the closure of C c (X ♥ ) with respect to ·, · ♥ by Theorem 3.63 of [48]. It is not hard to see then that any g ∈ D ♥ with g(♥) = 0, i.e., any g ∈ D can be approximated by elements of C c (X ♥ ) with g(♥) = 0 with respect to ·, · ♥ . Let now f ∈ D ♥ with L ♥ f (x) = 0 for all x ∈ X be given. Reading the corresponding part of the previous proof backwards, we then find that 0 = f, g ♥ for all g ∈ C c (X). By the discussed denseness of these g, we obtain that f is orthogonal to D.
As an application, we have a look at the metric ̺. We set By ̺ we denote the respective metric on the original graph (b, c). Proof. The first inequality is clear, as the set over which the supremum is taken is bigger. On the other hand, for f ∈ D ♥ we use the decomposition f = f o + f h from the previous theorem. As f o and f h are orthogonal with respect to ·, · ♥ , we obtain Q ♥ (f o , f h ) = 0. Thus, if Q ♥ (f ) ≤ 1, we have Q(f o ) ≤ 1 and Q ♥ (f h ) ≤ 1. Taking suprema over the relevant sets we obtain the claim.
As a second application, we consider length metrics. We now consider the set of all paths over X ♥ and denote by : (x 0 , . . . , x n ) is a path from x to y} where d is the corresponding metric over paths in X as before. If c > 0, then d c (x, y) is the infimum of lengths of paths connecting x and y in X, where the length of an edge is given by ℓ c (x, y) = c(x) −1 + c(y) −1 .
As the set of paths joining x and y in the graph X is smaller than the corresponding set in X ♥ , we obtain d ♥ (x, y) ≤ d(x, y) and d ♥ (x, y) ≤ d c (x, y). Furthermore, we obtain the following improved version of Lemma 3.4. In particular, we have ̺ 2 ≤ d ♥ .
Proof. The proof of Lemma 3.4 shows that this inequality holds for all f ∈ D ♥ with Q ♥ (f ) in place of Q(f ). As Q ♥ agrees with Q on D we obtain the inequality. The second claim follows from the proposition above.
We finish this section with a short discussion concerning the case when c is not summable. Let {X i | i ∈ I} be a partition of X, where I is a countable set, such that, for all i ∈ I, we have x∈X i c(x) < ∞. To each such X i , we can adjoin an element ♥ i . In particular, an analogous decomposition as above is valid. In the case of a finite I, one gets that the space of harmonic functions is |I| dimensional. Denoting by ̺ I and d I the respective metrics on the supergraph, we obtain similar results as above for each partition. In particular, we can consider the infimum of these metrics over all partitions and we obtain also analogous versions of the previous results.
Appendix B. Royden compactification for graphs with c ≡ 0 So far, the Royden compactification has only been considered for graphs with vanishing killing term c. Here, we show how to construct a compactification for general graphs (b, c) over X. The construction is a rather direct modification of the construction of the Royden compactification for graphs of the form (b, 0) as presented, e.g., in [48]. For this reason, we continue to refer to the outcome as the Royden compactification. We also shortly discuss how this (generalized) construction of the Royden compactification is stable under replacing (b, 0) by (b, c) with summable c.
Let (b, c) be a graph over X with associated form Q and consider the space B := D ∩ ℓ ∞ (X) with the norm u Q,∞ := Q(u) 1/2 + u ∞ .
The following lemma is well-known.
Lemma B.1. For any f, g ∈ B the product f g belongs to B and the inequality Q(f g) ≤ f ∞ Q(g) 1/2 + g ∞ Q(f ) 1/2 2 holds.
Theorem B.2. When equipped with · Q,∞ , the space B becomes a Banach algebra.
Remark. In the case c ≡ 0, the algebra B is called the Dirichlet algebra [48, Theorem (6.2)].
Proof. By the first part of the previous lemma, the space B is an algebra. Moreover, the inequality in the previous lemma easily gives that · Q,∞ is submultiplicative, i.e., satisfies It remains to show that B is complete with respect to · Q,∞ . Let (f n ) be a Cauchy sequence with respect to · Q,∞ . Then, it is a Cauchy sequence with respect to · ∞ . Hence, it converges uniformly to a function f on X. In particular, it converges pointwise to f . Now, an application of Fatou's lemma gives, for any natural number n, the estimate The previous theorem shows that we can associate to any graph (b, c) over X a commutative Banach algebra (B, · Q,∞ ). We now apply the Gelfand theory of commutative Banach algebras. Recall that C 0 (Y ) denotes the space of continuous functions vanishing at infinity whenever Y is a locally compact Hausdorff space. Theorem B.3. Let (b, c) be a graph over X and (B, · Q,∞ ) the associated Banach algebra. Then, there exists a unique (up to homeomorphism) locally compact Hausdorff space Y containing X such that the following assertions hold: (1) The set X is a dense open subset of Y .
(2) Any function in B can be extended to an element of C 0 (Y ).
(3) The algebra B separates points of Y .
(4) The algebra B does not vanish on any point of Y . If the constant function 1 belongs to B, then Y is compact.
Proof. Note that, by the Stone-Weierstrass theorem, (2), (3) and (4) just say that the algebra B is dense in C 0 (Y ) with respect to · ∞ . This easily shows uniqueness of Y up to homeomorphism (as C 0 (Y ) determines Y ).
To show existence we consider the set Y 0 of all multiplicative linear functionals on B. This set is a compact space in the weak- * -topology and contains the zero functional γ ∞ . We will show that the locally compact space Y := Y 0 \ {γ ∞ } has the desired properties.
Obviously, Y contains the set X as any x ∈ X provides a nonvanishing multiplicative functional via point evaluation. By the definition of the weak- * -topology, the functions of B can be considered as continuous functions on Y 0 which obviously vanish at γ ∞ . They therefore belong to C 0 (Y ).
Moreover, as the characteristic function of any x ∈ X is obviously an element of B, it is continuous on Y and hence any point x ∈ X is an open set in Y .
By construction, the algebra B separates points of Y and does not vanish on any point of Y . By the Stone-Weierstrass theorem, it is then dense in C 0 (Y ) and this implies that X is dense in Y .
This shows that Y indeed has all of the desired properties. It remains to show the last statement. If the constant function 1 belongs to B, then the set Y of all non-vanishing multiplicative functionals on B can easily be seen to be a closed subset of Y 0 . As a closed subset of a compact space, Y is then compact as well.
Remarks. (a) Note that the constant function 1 belongs to B if and only if c is summable.
(b) If the constant function 1 belongs to B, then property (4) of the above theorem is trivially satisfied and, in (3), the space C 0 (Y ) is just the space C(Y ).
(c) From (a) and (b) we see that if c ≡ 0, then the constant function 1 belongs to B and the compact space Y is characterized by (1), (2) and (3). In this way, we recover Theorem 6.4 of [48].
(d) It is not hard to see that B does not change if (b, 0) is replaced by (b, c) with summable c. Moreover, the corresponding norms can easily be seen to be equivalent. Thus, the space Y does not change when one replaces (b, 0) by (b, c) with summable c.
Definition B.4. The Royden compactification of the graph (b, c) over X is defined to be the space Y from the previous theorem if c is summable and to be the one-point compactification of Y , otherwise.