# A study of 2-ended graphs via harmonic functions

Agelos Georgakopoulos Supported by EPSRC grants EP/V048821/1 and EP/V009044/1.
Alex Wendland

###### Abstract

We prove that every recurrent graph $G$ quasi-isometric to $\mathbb{R}$ admits
an essentially unique Lipschitz harmonic function $h$. If $G$ is vertex-
transitive, then the action of $Aut(G)$ preserves $\partial h$ up to a sign, a
fact that we exploit to prove various combinatorial results about $G$. As a
consequence, we prove the 2-ended case of the conjecture of Grimmett & Li that
the connective constant of a non-degenerate vertex-transitive graph is at
least the golden mean.

Moreover, answering a question of Watkins from 1990, we construct a cubic,
2-ended, vertex-transitive graph which is not a Cayley graph.

Keywords: 2-ended graph, Lipschitz harmonic function, vertex-transitive,
Cayley graph, connective constant, golden mean, electrical current, quasi-
isometry.

MSC 2020 Classification: 31C05, 31C20, 05C63, 05E18, 05C21, 05C50, 60J45,
31C12.

##  1 Introduction

An influential paper of Kleiner [21] provides a proof of Gromov’s polynomial
growth theorem using harmonic functions on Cayley graphs. Shalom & Tao [27]
refined Kleiner’s method providing tighter quantitative results, thereby
proving that every finitely generated Cayley graph $G\ $admits a non-constant
Lipschitz harmonic function, and if $G\ $has polynomial growth, then the
vector space of those functions has finite dimension. These proofs triggered
significant interest in the study of Lipschitz harmonic functions on graphs,
see [3, 4, 20] and references therein. The study of harmonic functions with
restrictions on their growth is classical in Riemannian geometry [6, 7, 31],
and the origins of the aforementioned proofs can be found there; see [19] for
a nice overview.

Our first result provides the exact dimension of the (real) vector space of
Lipschitz harmonic functions on a 2-ended Cayley graph $G$, and more generally
on graphs that asymptotically resemble $\mathbb{R}$. Recall that a function
$h:V(G)\to\mathbb{R}$ is _harmonic_ , if $h(v)$ equals the average of $h(u)$
over the neighbours $u$ of $v$, and it is _Lipschitz_ , if $|h(v)-h(u)|<C$
holds for a fixed constant $C$ and every edge $vu\in E(G)$.

######  Theorem 1.1.

Let $G\ $be a locally finite, recurrent graph which is quasi-isometric to
$\mathbb{R}$. Then the vector space of Lipschitz harmonic functions on $G\
$has dimension equal to 2.

In other words, every such graph admits a non-constant Lipschitz harmonic
function, which is unique up to an additive and a multiplicative constant.

We remark that since recurrence is preserved under quasi-isometries between
bounded degree graphs [25, THEOREM 3.2], we can replace the recurrence
condition by the bounded degree condition in Theorem 1.1. Theorem 1.1 probably
applies to Riemannian manifolds of bounded geometry that are quasi-isometric
to $\mathbb{R}$, with a similar proof.

The type of harmonic functions supported by a graph or manifold is in general
unstable under quasi-isometries [2, 24], and so it is not easy to deduce
Theorem 1.1 from the analogous statement for $\mathbb{R}$ or $\mathbb{Z}$. Our
proof of Theorem 1.1 is not difficult, but uses a mixture of ingredients
involving physical intuition around electrical networks, coarse geometry, and
the classical fact that a recurrent graph admits no positive, non-constant,
harmonic functions. The main message of this paper is perhaps that Theorem 1.1
has direct implications for the combinatorial structure of 2-ended vertex-
transitive graphs. We say that a graph is _$k$ -regular_ if all its vertices
have degree $k$, and say that it is _cubic_ if it is $3$-regular. As a first
application, we use Theorem 1.1 to prove

######  Corollary 1.2.

Every cubic, 2-ended, vertex-transitive graph $G\ $is 3-edge-colourable.

Since transitive graphs are regular, we immediately deduce from this that the
edge set of $G\ $decomposes into three perfect matchings. Cubic graphs are
special among the 2-ended, vertex-transitive graphs in that they cannot arise
as a cartesian product of a finite graph and a 2-way infinite path, and so
understanding the cubic case is an important first step towards understanding
all 2-ended vertex-transitive graphs.

We remark that it is a well-known open problem whether every finite, cubic,
Cayley graph is $3$-edge-colourable [1]. It is known that every infinite,
connected, vertex-transitive graph admits a perfect matching [8, 22].

Using Theorem 1.1 again, we obtain a simple proof of a theorem of Watkins [29]
saying that every 2-ended edge-transitive graph has even vertex degrees
(Corollary 4.1).

Techniques using electrical networks or harmonic functions have found many
applications, but usually to the study of stochastic processes or analytic
aspects of graphs; see e.g. [10, 12, 18, 23]. Purely combinatorial
implications like the above are perhaps more surprising.

The _connective constant $\mu(G)$_ of an infinite graph $G\ $is the
exponential growth rate of self-avoiding walks in $G\ $starting at a fixed
vertex. This invariant is of great interest to the statistical mechanics
community, see e.g. [9, 16] and references therein. As another consequence of
Theorem 1.1, we prove

######  Theorem 1.3.

Every 2-ended vertex-transitive graph $G\ $satisfies $\mu(G)\geq\phi$, where
$\phi:=\frac{1+\sqrt{5}}{2}$ is the golden mean.

This settles the 2-ended case of a conjecture of Grimmett & Li [17] stating
that $\mu(G)\geq\phi$ holds for every infinite, vertex-transitive $G$ other
than the 2-way infinite path. Grimmett & Li [17] proved the special case of
Theorem 1.3 where $G\ $is a Cayley graph, and our approach via harmonic
functions closely follows theirs. They thereby revived an old question of
Watkins [28], asking whether there is a cubic, 2-ended, vertex-transitive
graph which is not a Cayley graph. In Section 5 we answer this question by
constructing111This construction was originally announced in the arXiv version
of [13], but following a referee suggestion it was removed from the journal
version. such a graph:

######  Theorem 1.4.

There is a cubic, 2-ended, vertex-transitive graph which is not isomorphic to
any Cayley graph.

In Section 6 we ask if every such graph is bi-Cayley, along with further
problems motivated from the above results.

The following folklore open problem emerged naturally from the aforementioned
result of Shalom & Tao [27]:

######  Problem 1.1.

Does every locally finite vertex-transitive graph $G\ $admit a non-constant
Lipschitz harmonic function?

Proposition 3.1 below answers this in the affirmative in the (easier) case
where $G\ $has at least two ends. The difficult case is where $G\ $has
intermediate growth.

##  2 Preliminaries

Let $G\ =(V,E)$ be a graph, with vertex set $V$ and edge set $E$. The _degree
$d(v)$_ of a vertex $v\in V$ is the number of edges incident with $v$. We say
that $G\ $is _locally finite_ , if $d(v)<\infty$ for every $v\in V$. All our
graphs below are locally finite.

A 1-way infinite path is called a _ray_. Two rays in $G\ $are _equivalent_ ,
if no finite set of edges separates them. The corresponding equivalence
classes of rays are the _ends_ of $G$. We say that an end $\epsilon$ _lives_
in a set $X\subseteq V$, if for each ray $R$ in $\epsilon$, all but finitely
many vertices of $R$ lie in $X$.

A _cut_ of $G\ $is a bipartition $(X,Y)$ of $V$. We sometimes identify this
cut with the set _$E(X,Y):=\\{xy\in E\mid x\in X,y\in Y\\}$_ of edges crossing
it. It is not hard to prove that for every two ends $\epsilon,\zeta$ of $G$,
there is a cut $(X,Y)$ such that $\epsilon$ lives in a $X$, and $\zeta$ lives
in a $Y$, and $E(X,Y)$ is finite.

A graph can be thought of as a metric space by endowing it with the graph
distance $d$. A _quasi-isometry_ between graphs $G=(V,E)$ and
$H=(V^{\prime},E^{\prime})$ is a map $f:V\to V^{\prime}$ such that the
following hold for fixed constants $M\geq 1,A\geq 0$:

  1. (i)

$M^{-1}d(x,y)-A\leq d(f(x),f(y))\leq Md(x,y)+A$ for every $x,y\in V$, and

  2. (ii)

for every $z\in V^{\prime}$ there is $x\in V$ such that $d(z,f(x))\leq A$.

We say that $G$ and $H$ are _quasi-isometric_ , if such a map $f$ exists. We
will use the following well-known fact:

######  Proposition 2.1 ([5, Proposition 2.2]).

Quasi-isometric locally finite graphs have the same number of ends.

Let $\mbox{Aut}(G)$ denote the group of automorphisms of $G$. We say that $G\
$is _vertex-transitive_ , if for every $x,y\in V$ there is $z\in\mbox{Aut}(G)$
such that $z(x)=y$.

##  3 Proof of Theorem 1.1

In this section we prove Theorem 1.1. Let $LH(G)$ denote the real vector space
of Lipschitz harmonic functions on a graph $G$. We start with the lower bound
$\dim(LH(G))\geq 2$, which we can prove in greater generality as follows:

######  Proposition 3.1.

Every connected, locally finite graph with more than one end admits a non-
constant Lipschitz harmonic function.

This provides a positive answer to Problem 1.1 in the multi-ended case. We
will construct the desired harmonic function as a limit of ‘electrical
potentials’ along an increasing sequence of finite subgraphs, corresponding to
an electrical current of fixed intensity flowing through a cut separating the
ends. We thereby exploit the frequently used viewpoint of harmonic functions
as electrical potentials. We start by recalling the relevant electrical
network theory.

###  3.1 Harmonic functions and electrical network basics

Let $G=(V,E)$ be a (finite or infinite) graph. Let $\vec{E}$ denote the set of
ordered pairs $(x,y)$ with $xy\in E$. We write $\overrightarrow{xy}$ to denote
$(x,y)$. Note that for every $xy\in E$, both $\overrightarrow{xy}$,
$\overrightarrow{yx}$ ($=:\overleftarrow{xy}$) lie in $\vec{E}$.

We say that a function $f:\vec{E}\rightarrow\mathbb{R}$ is _antisymmetric_ ,
if $f(\overrightarrow{xy})=-f(\overleftarrow{xy})$ for every $xy\in E$. All
functions we consider from now on are antisymmetric.

Given $f:\vec{E}\rightarrow\mathbb{R}$, we write _$f^{*}(x):=\sum_{y\sim
x}f(\overrightarrow{xy})$_ for the net flow of $f$ out of $x$. Here _$y\sim
x$_ means that $xy\in E$.

Fix a graph $G=(V,E)$ for the rest of this section.

######  Definition 3.2.

We say that an antisymmetric function $f:\vec{E}\to\mathbb{R}$ satisfies
_Kirchhoff’s Node Law (KNL)_ at a vertex $x$, if $f^{*}(x)=0$ holds.

We say that $f$ is a _(sourceless) flow_ if it satisfies KNL at every $x\in
V$.

Intuitively, KNL says that current is preserved at $x$. Given $p\neq q\in V$,
we say that $f:\vec{E}\to\mathbb{R}$ is a _$p-q$ flow_, or a flow from $p$ to
$q$, if (KNL) holds for every $x\not\in\\{p,q\\}$, and $f$ is antisymmetric.
The _intensity_ of $f$ is defined as $f^{*}(p)$. If $G\ $is finite, then one
can easily show that $f^{*}(q)=-f^{*}(p)$ by applying KNL to each other
vertex.

######  Definition 3.3.

We say that a flow $f:\vec{E}\to\mathbb{R}$ satisfies _Kirchhoff’s Cycle Law
(KCL)_ , if for every closed walk (equivalently for every cycle)
$x_{0},x_{1},\ldots,x_{n}(=x_{0})$ in $G\ $we have
$\sum_{i=0}^{n-1}f(\overrightarrow{x_{i}x_{i+1}})=0$.

######  Definition 3.4.

An _(electrical) current_ of intensity $I\in\mathbb{R}$ from $p$ to $q$ in
$G$, is a $p$-$q$ flow $i:\vec{E}\to\mathbb{R}$ satisfying Kirchhoff’s Cycle
Law, such that $i^{*}(p)=I=-i^{*}(q)$.

We say that a pair of functions $i:\vec{E}\to\mathbb{R}$,
$u:V\rightarrow\mathbb{R}$ satisfies _Ohm’s Law (OL)_ , if
$i(\overrightarrow{xy})=u(x)-u(y)$ holds for every $x,y\in V$.

Note that if $i,u$ satisfies (OL), then so does $i,(u+a)$ for every constant
$a\in\mathbb{R}$. We say that $i$ is the _Ohm dual_ of $u$ and $u$ is an Ohm
dual of $i$, if (OL) holds.

######  Definition 3.5.

We say that a function $u:V\to\mathbb{R}$ is _harmonic_ , if $u(x)=\sum_{y\sim
x}u(y)/d(x)$ holds for every $x\in V$.

######  Proposition 3.6.

If the pair $i,u$ satisfies Ohm’s Law, then $u$ is harmonic at $x\in V$ if and
only if $i$ satisfies Kirchhoff’s Node Law at $x$, i.e. if $i^{*}(x)=0$.

This is well-known, but we include the proof for convenience as it is quite
short:

###### Proof.

Since $i,u$ satisfy (OL), we have

$\sum_{y\sim x}u(y)=\sum_{y\sim
x}\big{(}u(x)-i(\overrightarrow{xy})\big{)}=d(x)u(x)-\sum_{y\sim
x}i(\overrightarrow{xy}),$

which is by definition equal to $d(x)u(x)-i^{*}(x)$. Thus $i^{*}(x)=0$ if and
only if $\sum_{y\sim x}u(y)/d(x)=u(x)$, which is the definition of being
harmonic. ∎

######  Proposition 3.7 (The maximum/minimum principle [11, Lemma 3.2]).

Suppose $G\ $is finite and connected, and $u:V\to\mathbb{R}$ is harmonic at
every vertex of $V^{\prime}\subset V$. If the maximum or minimum of $u$ is
achieved at some vertex of $V^{\prime}$, then $u$ is constant.

Note that every function $u:V\to\mathbb{R}$ has a (unique) Ohm dual _$\partial
u$_ defined by $\partial u(\overrightarrow{xy})\mapsto u(x)-u(y)$. For the
converse we have the following well-known fact:

######  Proposition 3.8 ([11, Proposition 3.7.]).

Let $G$ be a connected graph, and $i:\vec{E}\to\mathbb{R}$ antisymetric. Then,
there is $u:V\rightarrow\mathbb{R}$ such that the pair $i,u$ satisfies OL if
and only if $i$ satisfies KCL. This $u$ is unique up to an additive constant.

Perhaps better-known among electrical engineers, is the fact that no branch of
an electrical network $G\ $can enhance the current flowing into $G$ from the
external source:

######  Proposition 3.9.

Let $G=(V,E)$ be a finite graph, and $p,q\in V$. Let $f:\vec{E}\to\mathbb{R}$
be the $p$–$q$ electrical current of intensity 1 in $G$. Then
$|f(\overrightarrow{wv})|\leq 1$ holds for every
$\overrightarrow{wv}\in\vec{E}$.

###### Proof.

Let $h$ be an Ohm dual of $f$ as provided by Proposition 3.8. Given an edge
$wv\in E$, let

$A:=\\{x\in V\mid h(x)\geq\frac{h(w)+h(v)}{2}\\}$

and $Z:=V\backslash A$. Thus the cut $(A,Z)$ separates $w,v$ whenever
$f(\overrightarrow{wv})\neq 0$, which we may assume is the case. Note that

$f(\overrightarrow{xz})>0$ holds for every $x\in A,z\in Z$. (1)

Moreover, we have $\sum_{x\in A}f^{*}(x)\leq 1$ since $f$ is a current of unit
intensity. By double counting, we have $\sum_{x\in A}f^{*}(x)=\sum_{x\in
A,z\in Z}f(\overrightarrow{xz})\geq|f(\overrightarrow{wv})|$, where the last
inequality follows from (1) and the fact that $(A,Z)$ separates $w,v$.
Combining these two inequalities we obtain the desired
$|f(\overrightarrow{wv})|\leq 1$. ∎

###  3.2 Existence of Lipschitz harmonic functions

We have now gathered the necessary ingredients to prove our existence result:

###### Proof of Proposition 3.1.

Assume first that $G\ $has exactly two ends $\epsilon,\zeta$; the general case
is similar.

Fix an _origin_ $o\in V(G)$, and consider the _spheres_ $S_{n}:=\\{v\in
V(G)\mid d(o,v)=n\\}$. The _ball_ $B_{n}$ is the subgraph of $G\ $induced by
the vertex set $\\{v\in V(G)\mid d(o,v)\leq n\\}$. Define, for each
${n\in\mathbb{N}}$, the _layer_ $L_{n}$ (respectively $L_{-n}$) as the subset
of $S_{n}$ contained in the unique component of $G-B_{n-1}$ containing a ray
of $\epsilon$ (resp. $\zeta$). Note that $L_{n}$ coincides with $L_{-n}$ as
long as $B_{n-1}$ does not separate the two ends, but $L_{n},L_{-n}$ are
disjoint for $n>n_{0}:=\min\\{k\mid B_{k}\text{ separates }\epsilon,\zeta\\}$.

For each $n>n_{0}$, we define a flow $f_{n}$ in $B_{n}$ as follows. Pick
vertices $p\in L_{n},q\in L_{-n}$, and let $f_{n}$ be the electrical current
of intensity 1 from $p$ to $q$ in $B_{n}$.

Moreover, for every cut $C=E(X,Y)$ of $B_{n}$ separating $L_{n}$ from
$L_{-n}$, the net flow of $f_{n}$ through $C$ equals 1 because the net flow of
$f_{n}$ out of $L_{n}$ is 1, and every vertex outside $L_{n}\cup L_{-n}$
preserves the net flow. Fix such a cut $C$ in $B_{n_{0}+1}$, and note that $C$
separates $\epsilon$ from $\zeta$ in $G$, and therefore it separates $L_{i}$
from $L_{-i}$ for every $i>n_{0}$.

Let $f:\vec{E}(G)\to\mathbb{R}$ be a pointwise accumulation point of the
sequence $(f_{n})_{n\in\mathbb{N}}$, which exists since the space
$[-1,1]^{\vec{E}(G)}$ in which our functions live is compact by Tychonoff’s
theorem.

Then $f$ is not identically 0, because its net flow through the finite cut $C$
equals 1. Moreover, $f$ satisfies Kirchhoff’s cycle law for every cycle $K$ of
$G$, since every $f_{n}$ does. Thus we can define the Ohm dual $h$ of $f$
satisfying $h(o)=0$ by Proposition 3.8. Finally, $f$ satisfies Kirchhoff’s
node law at every vertex $v\in V(G)$, since almost every $f_{n}$ does.
Therefore $h$ is a harmonic function by Proposition 3.6. It is non-constant
since $f$ is not identically 0. By Proposition 3.9, we have
$|f_{n}(\vec{e})|\leq 1$ for every $\vec{e}\in\vec{E}$, and hence
$|f(\vec{e})|\leq 1$, which means that $h$ is Lipschitz.

If $G\ $has more than two ends, we can repeat the construction using an
appropriate bipartition of the ends as follows. We let $C$ be a minimal cut
separating two infinite components $K_{1},K_{2}$. Let $n_{0}:=\min\\{k\mid
C\subset B_{k}\\}$. For $n>n_{0}$, define $L_{n}:=S_{n}\cap K_{1}$ and
$L_{-n}:=S_{n}\cap K_{2}$. The rest of the construction of $h$ remains the
same. ∎

###  3.3 Upper bounding $\dim(LH(G))$

Our proof of Theorem 1.1 will come as a combination of the above and the
following lemmas. Given a cut $(X,Y)$ of a graph $G$, and a flow
$f:\vec{E}(G)\to\mathbb{R}$, we define _$f(X,Y):=\sum_{x\in X,y\in
Y}f(\overrightarrow{xy})$_.

######  Lemma 3.10.

Let $G=(V,E)$ be a connected, 2-ended graph. For every sourceless flow
$f:\vec{E}\to\mathbb{R}$, and every two finite cuts $(X,Y)$ and
$(X^{\prime},Y^{\prime})$ separating the ends, we have $f(X,Y)=\sigma
f(X^{\prime},Y^{\prime})$, where $\sigma=1$ if $X,X^{\prime}$ contain the same
end, and $\sigma=-1$ otherwise.

###### Proof.

Let $\epsilon$ be the end of $G\ $that lives in $X$, and $\zeta$ the end that
lives in $Y$. We claim that if $\epsilon$ lives in $X^{\prime}$, then the
symmetric difference $F=X\triangle X^{\prime}:=(X\backslash
X^{\prime})\cup(X^{\prime}\backslash X)$ is finite. For if not, then one of
$X,X^{\prime}$ contains an infinite sequence $\\{v_{i}\\}$ of vertices not
contained in the other, and as $v_{i}$ must converge to $\epsilon$ we have a
contradiction.

Next, we claim that $f(X^{\prime},Y^{\prime})=f(X,Y)+\sum_{v\in F}f^{*}(v)$.
This is easy to check by induction on the size of $F$, because the effect on
$f(X,Y)$ of moving a vertex $v$ from $Y$ to $X$ is exactly the addition of
$f^{*}(v)$. Since $f^{*}(v)=0$ for every $v$ as $f$ is a sourceless flow, we
deduce $f(X,Y)=f(X^{\prime},Y^{\prime})$.

If $\epsilon$ lives in $Y^{\prime}$ instead, then we repeat the same arguments
with the roles of $X^{\prime}$ and $Y^{\prime}$ interchanged, to deduce that
$f(X,Y)=f(Y^{\prime},X^{\prime})=-f(X^{\prime},Y^{\prime})$. ∎

######  Lemma 3.11.

Let $G=(V,E)$ be a locally finite, recurrent graph which is quasi-isometric to
$\mathbb{R}$. Let $h$ be a Lipschitz harmonic function on $G$, and suppose
that for some finite cut $E(X,Y)$ separating the two ends of $G\ $we have
$\partial h(X,Y)=0$. Then $h$ is constant.

###### Proof.

By Proposition 2.1, $G$ has exactly two ends $\epsilon,\zeta$.

It is well-known that every recurrent graph has no non-constant positive
harmonic functions [30, Theorem (1.16)]222The analogous statement for
Riemannian manifolds is also true [14, Theorem 5.1].. It follows from this
that if $h$ is non-constant, then it is unbounded both above and below. Thus
there is a sequence $(v_{n})_{n\in\mathbb{N}}$ of vertices such that
$h(v_{n})\to\infty$. Some subsequence of $(v_{n})_{n\in\mathbb{N}}$ converges
to one of the ends, and so we may assume without loss of generality that
$v_{n}\to\epsilon$.

Next, we claim that

for every sequence $(w_{n})_{n\in\mathbb{N}}$ of vertices of $G\ $that
converges to $\epsilon$, we have $h(w_{n})\to\infty$. (2)

To see this, given $v\in V$, let $S_{v}\subset G$ be a connected subgraph
containing $v$ and separating $\epsilon$ from $\zeta$. Using a quasi-isometry
$q:G\to\mathbb{R}$, it is not hard to choose the $S_{v}$ to have diameters
$\mathrm{diam}(S_{v})<M$ for a constant $M$ depending on $q$ but not on $v$.

Since $h$ is Lipschitz, it follows that if $x,y\in S_{v}$, then
$|h(x)-h(y)|<M^{\prime}\in\mathbb{R}$. Thus

$h[S_{v_{n}}]\to\infty$ for the above sequence $(v_{n})_{n\in\mathbb{N}}$. (3)

Next, let $H^{\prime}_{i}$ denote the union of the finite components of
$G-(S_{v_{i}}\cup S_{v_{i+1}})$, and let $H_{i}:=H^{\prime}_{i}\cup
S_{v_{i}}\cup S_{v_{i+1}}$. Notice that $H_{i}$ is a finite graph. Thus (3),
combined with the maximum principle (Proposition 3.7), implies that
$h[H_{n}]\to\infty$. Since $(v_{n})_{n\in\mathbb{N}},(w_{n})_{n\in\mathbb{N}}$
both converge to $\epsilon$, almost every $w_{n}$ lies in some $H_{i(n)}$ with
$i(n)\to\infty$ as $n\to\infty$. The last two remarks combined imply
$h(w_{n})\to\infty$ as claimed.

Since $h$ is also not bounded below, we obtain a sequence
$(z_{n})_{n\in\mathbb{N}}$ of vertices such that $h(z_{n})\to-\infty$. Since
no subsequence of $(z_{n})_{n\in\mathbb{N}}$ can converge to $\epsilon$ by
(2), it follows that $z_{n}\to\zeta$. By repeating the proof of (2) we deduce
that $h(y_{n})\to-\infty$ holds whenever $y_{n}\to\zeta$.

Let $P:=\\{x\in V(G)\mid h(x)\geq 0\\}$, and $N:=V\backslash P=\\{x\in
V(G)\mid h(x)<0\\}$. Note that the cut $E(P,N)$ is non-empty. We claim that
$E(P,N)$ consists of finitely many edges. For if ${x_{n}}$ is a sequence of
distinct end-vertices of edges in $E(P,N)$ lying in $P$, then some subsequence
will converge to $\epsilon$ or $\zeta$. We would then have
$|h(x_{n})|\to\infty$ by (2) and its analogue for $\zeta$. But this is
impossible: since $h$ is Lipschitz, and $x_{n}$ has a neighbour in $N$, the
values $h(x_{n})$ must be uniformly bounded.

Recall that we are assuming $\partial h(X,Y)=0$, and therefore Lemma 3.10
implies $\partial h(P,N)=0$. This is impossible, because $E(P,N)$ is non-
empty, and $\partial h(x,y)>0$ holds for every $xy\in E(P,N)$ with $x\in
P,y\in N$. This contradiction proves that $h$ is constant as claimed. ∎

###  3.4 Completing the proof of Theorem 1.1

Our main result now follows as a direct combination of Proposition 3.1 and
Lemma 3.11:

###### Proof of Theorem 1.1.

By Proposition 2.1, $G$ has exactly two ends $\epsilon,\zeta$. To see that
$\dim(LH(G))\geq 2$, let $f_{1}\equiv 1$, and let $f_{2}$ be a non-constant
Lipschitz harmonic function of $G\ $as provided by Proposition 3.1. Then
$f_{1},f_{2}$ clearly span a 2-dimensional subspace of $LH(G)$.

For the converse inequality, fix a finite cut $E(X,Y)$ of $G\ $separating
$\epsilon,\zeta$. We claim that if two functions $h_{1},h_{2}\in LH(G)$
satisfy $\partial h_{1}(X,Y)=\partial h_{2}(X,Y)$ and $h_{1}(o)=h_{2}(o)$ for
some $o\in V(G)$, then $h_{1}=h_{2}$ holds. This clearly implies that
$\dim(LH(G))\leq 2$.

To prove this claim, let us consider the difference $h:=h_{1}-h_{2}\in LH(G)$.
Notice that $\partial h(X,Y)=0$. Thus Lemma 3.11 says that $h$ is constant,
and since $h_{1}(o)=h_{2}(o)$ we deduce that $h\equiv 0$ and so $h_{1}=h_{2}$.
∎

Let us explore the tightness of the conditions of the results of this section.

Proposition 3.1 fails if $G\ $is 1-ended, as can be easily checked by letting
$G\ $be a 1-way infinite path.

Theorem 1.1 (and Lemma 3.11) becomes false if we drop the recurrence
condition. To see this, start with the 2-way infinite ladder $L$, i.e. the
graph obtained from the disjoint union of two 2-way infinite paths
$H_{1},H_{2}$ by joining each vertex of $H_{1}$ to the corresponding vertex of
$H_{2}$ with an edge. We call the edges in each $H_{i}$ _horizontal_ , and the
remaining edges _vertical_. Obtain $G\ $by replacing each horizontal edge of
$L$ at distance $n$ from the origin by $2^{n}$ paths of length 2. The
interested reader will be able to construct a bounded harmonic function $h$
that converges to four different values as we move along the four horizontal
rays. One way of doing so is by noticing that simple random walk on $G\ $will
almost surely traverse only finitely many vertical edges, and defining $h(v)$
as the probability for random walk starting at $v$ to eventually stick to a
fixed horizontal ray.

Theorem 1.1 and Lemma 3.11 easily become false if we drop the quasi-isometry
condition, even if we assume 2-endedness: let $H$ be an 1-ended graph that
admits non-constant bounded harmonic functions, and connect two copies of $H$
by one edge.

If we drop the Lipschitz condition in Lemma 3.11 then we do get non-constant
harmonic functions, but the only examples I know grow exponentially in the
distance from a fixed origin. I suspect this cannot be improved:

######  Conjecture 3.1.

Let $G=(V,E)$ be a locally finite, recurrent graph which is quasi-isometric to
$\mathbb{R}$. Let $h$ be a harmonic function on $G$, and suppose that for some
finite cut $E(X,Y)$ separating the two ends of $G\ $we have $\partial
h(X,Y)=0$. Then $h$ is either constant or grows exponentially, i.e. there is a
constant $c>1$ and a sequence of vertices $(v_{n})_{n\in\mathbb{N}}$ such that
$|h(v_{n})-h(v_{0})|>c^{d(v_{n},v_{0})}$.

Proposition 3.1 shows that the condition $\partial h(X,Y)=0$ is crucial here.

##  4 Consequences for vertex-transitive graphs

In this section we employ Theorem 1.1 to obtain results about 2-ended vertex-
transitive graphs as mentioned in the introduction.

###  4.1 Connective constant

We now prove Theorem 1.3, which provides a lower bound on the connective
constant $\mu(G)$ of a 2-ended, cubic, vertex-transitive graph. We will
refrain from recalling the definition of $\mu(G)$ as we will never use it, and
refer the interested reader to [17].

###### Proof of Theorem 1.3.

We follow the approach of Grimmett & Li [17], who proved the statement for a
cubic Cayley graph $G$. The case of degree at least 4 had been settled earlier
by the same authors [15]. Their proof starts by constructing a non-constant
harmonic function $g$ of $G$, with the property that $g$ is _skew-difference-
invariant_ , i.e. for every $u,v\in V(G)$, and $z\in\mbox{Aut}(G)$, we have

$g(z(v))-g(z(u))=\sigma(z)(g(v)-g(u)),$ (4)

where $\sigma(z)\in\\{-1,1\\}$. The rest of their proof (starting at the top
of p. 34 of [17]) does not rely on the structure of $G\ $and can be repeated
verbatim. Thus it suffices to construct such a function $g$.

For this, let $g:V(G)\to\mathbb{R}$ be a non-constant, Lipschitz, harmonic
function, provided by Theorem 1.1. Given any automorphism $z\in\mbox{Aut}(G)$,
the function $g\circ z$ is also in $LH(G)$. By Theorem 1.1, $g\circ z$ equals
$g$ up to a multiplicative constant $c_{z}\in\mathbb{R}$ and an additive
constant $a_{z}$. Note that if $F$ is a finite cut of $G\ $separating the two
ends $\epsilon,\zeta$, then the net flow of $\partial g$ from the component of
$G-F$ containing $\epsilon$ to the component of $G-F$ containing $\zeta$ is
independent of the choice of $F$ up to a sign by Lemma 3.10. It follows that
$c_{z}=\pm 1$. Thus letting $\sigma(z):=c_{z}$ satisfies (4). ∎

###  4.2 No edge-transitive graphs with odd degrees

By adapting our last argument we can recover the following result of Watkins,
which is the main result of [29].

######  Corollary 4.1 ([29]).

If $G\ $is a 2-ended, edge-transitive graph, then every vertex of $G\ $has
even degree.

###### Proof.

Suppose $o\in V(G)$ has odd degree, and let again $g:V(G)\to\mathbb{R}$ be a
non-constant, Lipschitz, harmonic function, provided by Theorem 1.1. Let
$ou,ov$ be two edges of $o$ such that $|g(o)-g(u)|\neq|g(o)-g(v)|$, which
exist because by Proposition 3.6 the net flow of $\partial g$ out of $o$ is 0,
and $o$ has odd degree.

Since $G\ $is edge-transitive, there is an automorphism $z\in\mbox{Aut}(G)$
such that $z(ou)=ov$. Note that the function $g^{\prime}:=g\circ z$ is also in
$LH(G)$. By Theorem 1.1, $g\circ z$ equals $g$ up to a multiplicative constant
$c_{z}\in\mathbb{R}$ and an additive constant $a_{z}$. Pick a finite cut
$E(X,Y)$ separating the ends of $G$. By Lemma 3.10 we have $\partial
g(X,Y)=\pm\partial g^{\prime}(X,Y)$ because $\partial g^{\prime}(X,Y)=\partial
g(z(X),z(Y))$. Since $a_{z}$ does not influence $\partial g^{\prime}$, we
deduce $c_{z}=\pm 1$. But this contradicts our assumption
$|g(o)-g(u)|\neq|g(o)-g(v)|$. ∎

###  4.3 Colourings

###### Proof of Corollary 1.2.

Let $g\in LH(G)$ be as in the proof of Theorem 1.3, that is, non-constant and
skew-difference-invariant. Repeating an idea of Grimmett & Li [17], we let
$a\leq b\leq c$ denote the values of $g(v)-g(o)$ for $v$ a neighbour of $o\in
V(G)$, and note that since $a+b+c=0$ by Proposition 3.6, one of the following
three cases must occur if we rescale $g$ appropriately:

  * Case 1:

$(a,b,c)=(-1,0,1)$. In this case, colour all edges $uv$ with $g(u)-g(v)=0$
red. Notice that the remaining edges span a 2-regular subgraph $H$ of $G$.
Each component of $H$ is a 2-way infinite path or a cycle. Since each edge
$uv$ of such a cycle $C$ satisfies $|g(u)-g(v)|=1$, and the sum of $g(u)-g(v)$
along $C$ equals 0, we deduce that $C$ must contain an even number of edges.
Thus we can colour each component of $H$ blue-green in an alternating way.

  * Case 2:

$(a,b,c)=(-1/2,-1/2,1)$. Colour all edges $uv$ with $|g(u)-g(v)|=1$ red, and
repeat the argument of Case 1 to colour the remaining edges blue-green.

  * Case 3:

$a<b<0,-a-b=c$. This case is easy: we can just colour each edge $uv$ according
to $|g(u)-g(v)|$.

∎

##  5 A cubic 2-ended vertex-transitive graph which is not Cayley

Watkins [28] asked whether every 2-ended vertex-transitive graph can be
obtained via a certain product operation between a finite vertex-transitive
graph and the 2-way infinite path. A positive answer to Watkins’ question
would imply that every 2-ended cubic vertex-transitive graph is a Cayley
graph. Whether this is true was more recently explicitly asked by Grimmett &
Li [17] due to its relevance to Theorem 1.3. In this section we construct an
example of a 2-ended cubic vertex-transitive graph which is not a Cayley
graph, thus providing a negative answer to these questions.

Let $\Gamma$ be the graph with
$V(\Gamma)=\\{v_{n,k}|n\in{\mathbb{Z}},k\in{\mathbb{Z}}/10{\mathbb{Z}}\\}$ and

$E(\Gamma)=\\{v_{n,k}v_{n,k+1}\ |\ n\in{\mathbb{Z}},\
k\in{\mathbb{Z}}/10{\mathbb{Z}}\\}\cup\\{v_{n,2k+1}v_{n+1,4k+2}\ |\
n\in{\mathbb{Z}},\ k\in{\mathbb{Z}}/10{\mathbb{Z}}\\}.$

By construction, $\Gamma$ is a cubic graph. A useful way to think of this
graph is as a 2-way infinite stack of layers
$L_{n}:=\\{v_{n,k}|k\in{\mathbb{Z}}/10{\mathbb{Z}}\\}$. Each $L_{n}$ spans a
10-cycle, and between any two layers $L_{n}$ and $L_{n+1}$ there is a
Petersen-graph-like structure. Thus $\Gamma$ is clearly 2-ended, since
contracting each $L_{n}$ into a vertex transforms $\Gamma$ into a 2-way
infinite path. Checking that $\Gamma$ has all other desired properties is
rather routine, but we include the details for the sake of completeness.

######  Claim 1.

$\Gamma$ is vertex-transitive.

###### Proof.

We introduce the following two maps $\sigma,\tau:V(\Gamma)\to V(\Gamma)$,
which will allow us to map any vertex of $\Gamma$ to any other:

$\sigma(v_{n,k})=v_{n+1,k}\ \mbox{ and }\
\tau(v_{n,k})=\begin{cases}v_{-n,k+1}&\mbox{ if }n\equiv 0\mbox{ (mod
}4\mbox{)}\\\ v_{-n,3-k}&\mbox{ if }n\equiv 1\mbox{ (mod }4\mbox{)}\\\
v_{-n,k+9}&\mbox{ if }n\equiv 2\mbox{ (mod }4\mbox{)}\\\ v_{-n,7-k}&\mbox{ if
}n\equiv 3\mbox{ (mod }4\mbox{)}\end{cases}.$

Thus $\sigma$ just shifts all the layers up by 1, whereas $\tau$ rotates the
10-cycle on $L_{0}$ by one position, which flips the stack of layers by
mapping $L_{n}$ to $L_{-n}$, and inverts the orientation of the 10-cycles at
layers of odd index. It is easy to see that each of $\tau$ and $\sigma$ is a
bijection preserving edges, and so $\sigma,\tau\in\mbox{Aut}(\Gamma)$. Let
$G:=\langle\sigma,\tau\rangle\leq Aut(\Gamma)$ be the group of automorphisms
of $\Gamma$ generated by $\sigma$ and $\tau$. For any two vertices
$v_{n,k},v_{n^{\prime},k^{\prime}}\in V(\Gamma)$, we have

$\displaystyle\sigma^{n^{\prime}}\tau^{k^{\prime}-k}\sigma^{-n}(v_{n,k})=$
$\displaystyle\sigma^{n^{\prime}}\tau^{k^{\prime}-k}(v_{0,k})$
$\displaystyle=$ $\displaystyle\sigma^{n^{\prime}}(v_{0,k^{\prime}})$
$\displaystyle=$ $\displaystyle v_{n^{\prime},k^{\prime}}$

and so $G$ acts transitively on $V(\Gamma)$. This proves Claim 1. ∎

A classical theorem of Sabidussi [26] states that a graph $G\ $is isomorphic
to a Cayley graph if and only if there is a subgroup of $\mbox{Aut}(G)$ acting
_regularly_ , i.e. freely and transitively, on $V(G)$. For the purposes of
this paper, they reader may use Sabidussi’s theorem as the definition of a
_Cayley graph_. We will use this to prove that our $\Gamma$ is not a Cayley
graph.

######  Claim 2.

$G$ is not a regular subgroup of $\mbox{Aut}(\Gamma)$.

###### Proof.

We have

$\displaystyle\tau^{-3}\sigma\tau\sigma(v_{0,k})$
$\displaystyle=\tau^{-3}\sigma\tau(v_{1,k})$
$\displaystyle=\tau^{-3}\sigma(v_{-1,3-k})$
$\displaystyle=\tau^{-3}(v_{0,3-k})$ $\displaystyle=v_{0,-k}.$

This implies $\tau^{-3}\sigma\tau\sigma(v_{0,0})=v_{0,0}$, yet
$\tau^{-3}\sigma\tau\sigma\not=1_{\Gamma}$ as
$\tau^{-3}\sigma\tau\sigma(v_{0,1})=v_{0,9}$. Thus the action of $G$ on
$\Gamma$ is not free, proving Claim 2. ∎

We remind the reader the $n$th layer is denoted $L_{n}=\\{v_{n,k}|\
k\in{\mathbb{Z}}/10{\mathbb{Z}}\\}$ for $n\in{\mathbb{Z}}$ and we define the
partition $\mathcal{C}:=\\{L_{n}\ |\ n\in{\mathbb{Z}}\\}$ of $V(\Gamma)$.

######  Claim 3.

Let $\phi\in\mbox{Aut}(\Gamma)$ satisfy $\phi(L_{a})=L_{b}$. If for some
$\chi\in\mbox{Aut}(\Gamma)$ we have $\phi(x)=\chi(x)$ for every $x\in L_{a}$,
then $\phi=\chi$. Moreover, $\phi$ preserves the partition
$\mathcal{C}:=\\{L_{n}\ |\ n\in{\mathbb{Z}}\\}$.

###### Proof.

Observe that $\phi(v_{a+1,2k})$ and $\phi(v_{a-1,2k+1})$ are uniquely
determined by $\phi(x),x\in L_{a}$ because each vertex in $L_{b}$ has exactly
one neighbour outside $L_{b}$. This in turn uniquely determines
$\phi(v_{a+1,2k+1})$ and $\phi(v_{a-1,2k})$ by a similar argument. Continuing
like this, we see that
$\phi(\\{v_{a+\epsilon,k}|k\in{\mathbb{Z}}/10{\mathbb{Z}}\\})=\\{v_{b\pm\epsilon,k}|k\in{\mathbb{Z}}/10{\mathbb{Z}}\\}$
for $\epsilon\in\\{-1,1\\}$. By an inductive argument, this uniquely
determines $\phi$, and moreover $\phi$ preserves $\mathcal{C}$. ∎

######  Claim 4.

Any $\phi\in\mbox{Aut}(\Gamma)$ preserves the partition
$\mathcal{C}=\\{L_{n}|n\in{\mathbb{Z}}\\}$.

###### Proof.

If $\phi$ does not fix $\mathcal{C}$, then by Claim 3 we have
$\phi(L_{0})\not=L_{a}$ for every $a\in{\mathbb{Z}}$. It is not hard to see
that no 10-cycle of $\Gamma$ other than the $L_{i}$ separates $\Gamma$ into
two infinite components. This contradicts that $\phi$ is an automorphism. (An
alternative way of proving the claim is by using Watkins’s theorem that every
2-ended vertex-transitive and edge-transitive graph has even degree [28].) ∎

######  Claim 5.

Any $\phi\in\mbox{Aut}(\Gamma)$ is uniquely determined by $\phi(v_{0,1})$ and
$\phi(v_{0,2})$.

###### Proof.

Assume $\phi(v_{0,1})=v_{a,b}$. Then by Claim 4, $\phi(v_{0,2})\in
N(v_{a,b})\cap\\{v_{a,k}|k\in{\mathbb{Z}}/10{\mathbb{Z}}\\}=\\{v_{a,b+1},v_{a,b-1}\\}$.
In either case, by Claim 4 this uniquely determines $\phi(v_{0,k})$ for
$k\in{\mathbb{Z}}/10{\mathbb{Z}}$. By Claim 3, this uniquely determines
$\phi$. ∎

We remark that this implies
$\mbox{Stab}_{\mbox{Aut}(\Gamma)}(v_{0,0})=\langle\tau^{-3}\sigma\tau\sigma\rangle={\mathbb{Z}}/2{\mathbb{Z}}$.
So $\langle\tau,\sigma\rangle=\mbox{Aut}(\Gamma)$.

######  Claim 6.

$\Gamma$ is not isomorphic to a Cayley graph.

###### Proof.

Let $T\leq\mbox{Aut}(\Gamma)$ be a transitive subgroup. Thus we can find
automorphisms $\sigma^{\prime},\tau^{\prime}\in T$ such that
$\sigma^{\prime}(v_{0,1})=v_{1,1}$ and $\tau^{\prime}(v_{0,1})=v_{0,2}$. By
Claim 4, $T$ preserves the partition $\mathcal{C}$. So either
$\tau^{\prime}(v_{0,2})=v_{0,3}$ and $\tau^{\prime}=\tau$ or
$\tau^{\prime}(v_{0,2})=v_{0,1}$ and

$\tau^{\prime}(v_{n,k})=\sigma\tau\sigma(v_{n,k})=\tilde{\tau}(v_{n,k}):=\begin{cases}v_{-n,3-k}&\mbox{
if }n\equiv 0\mbox{ (mod }4\mbox{)}\\\ v_{-n,k-1}&\mbox{ if }n\equiv 1\mbox{
(mod }4\mbox{)}\\\ v_{-n,7-k}&\mbox{ if }n\equiv 2\mbox{ (mod }4\mbox{)}\\\
v_{-n,k+1}&\mbox{ if }n\equiv 3\mbox{ (mod }4\mbox{)}\end{cases}$

by Claim 5. Similarly, either $\sigma^{\prime}(v_{0,2})=v_{1,2}$ and
$\sigma^{\prime}=\sigma$ or $\sigma^{\prime}(v_{0,2})=v_{1,0}$ and

$\sigma^{\prime}(v_{n,k})=\sigma\tau^{-1}\sigma\tau\sigma(v_{n,k})=\tilde{\sigma}(v_{n,k}):=\begin{cases}v_{n+1,2-k}&\mbox{
if }n\equiv 0\mbox{ (mod }4\mbox{)}\\\ v_{n+1,4-k}&\mbox{ if }n\equiv 1\mbox{
(mod }4\mbox{)}\\\ v_{n+1,8-k}&\mbox{ if }n\equiv 2\mbox{ (mod }4\mbox{)}\\\
v_{n+1,6-k}&\mbox{ if }n\equiv 3\mbox{ (mod }4\mbox{)}\end{cases}.$

by Claim 5. By Claim 2, if
$\\{\sigma^{\prime},\tau^{\prime}\\}=\\{\sigma,\tau\\}$ then $T$ is not
regular. If $\\{\sigma^{\prime},\tau^{\prime}\\}=\\{\tilde{\sigma},\tau\\}$
then

$\displaystyle\tau\tilde{\sigma}\tau\tilde{\sigma}(v_{0,k})$
$\displaystyle=\tau\tilde{\sigma}\tau(v_{1,2-k})$
$\displaystyle=\tau\tilde{\sigma}(v_{-1,k+1})$ $\displaystyle=\tau(v_{0,5-k})$
$\displaystyle=v_{0,6-k}$

giving $\tau\tilde{\sigma}\tau\tilde{\sigma}(v_{0,3})=v_{0,3}$ yet
$\tau\tilde{\sigma}\tau\tilde{\sigma}\not=1_{\Gamma}$. Similarly, if
$\\{\sigma^{\prime},\tau^{\prime}\\}=\\{\sigma,\tilde{\tau}\\}$ then

$\displaystyle\tilde{\tau}\sigma\tilde{\tau}\sigma(v_{0,k})$
$\displaystyle=\tilde{\tau}\sigma\tilde{\tau}(v_{1,k})$
$\displaystyle=\tilde{\tau}\sigma(v_{-1,k-1})$
$\displaystyle=\tilde{\tau}(v_{0,k-1})$ $\displaystyle=v_{0,4-k}$

giving $\tilde{\tau}\sigma\tilde{\tau}\sigma(v_{0,2})=v_{0,2}$ yet
$\tilde{\tau}\sigma\tilde{\tau}\sigma\not=1_{\Gamma}$. Lastly, if
$\\{\sigma^{\prime},\tau^{\prime}\\}=\\{\tilde{\sigma},\tilde{\tau}\\}$ then

$\displaystyle\tilde{\tau}\tilde{\sigma}\tilde{\tau}\tilde{\sigma}(v_{0,k})$
$\displaystyle=\tilde{\tau}\tilde{\sigma}\tilde{\tau}(v_{1,2-k})$
$\displaystyle=\tilde{\tau}\tilde{\sigma}(v_{-1,1-k})$
$\displaystyle=\tilde{\tau}(v_{0,5+k})$ $\displaystyle=v_{0,-2-k}$

giving $\tilde{\tau}\tilde{\sigma}\tilde{\tau}\tilde{\sigma}(v_{0,9})=v_{0,9}$
yet $\tilde{\tau}\tilde{\sigma}\tilde{\tau}\tilde{\sigma}\not=1_{\Gamma}$.
Therefore $T$ is never regular, and so $\Gamma$ is not a Cayley graph by
Sabidussi’s theorem mentioned above. ∎

Combining the above claims proves Theorem 1.4.

We have implicitly proved that $\mbox{Aut}(\Gamma)=\langle\sigma,\tau\rangle$.
Some further study, for which we thank Derek Holt, can show that

$\mbox{Aut}(\Gamma)=\langle\sigma,\tau|\tau^{10},(\tau^{-1}\sigma\tau\sigma)^{2},\sigma^{-1}\tau^{2}\sigma\tau^{-4},(\sigma^{-2}\tau)^{2}\rangle.$

##  6 Further problems

In this paper we have used harmonic functions to deduce various facts about
2-ended, vertex-transitive graphs. We feel that the technique can be exploited
further to yield a better understanding of this class of graphs, possibly
leading to a complete description. Towards this aim, we propose

######  Problem 6.1.

Provide an effective enumeration of the family of 2-ended, locally finite,
vertex-transitive graphs.

By an _effective enumeration_ of a family $\mathcal{F}$ we mean an algorithm
that outputs a sequence of finite strings $(S_{n})_{n\in\mathbb{N}}$, such
that each $S_{i}$ _encodes_ an element of $\mathcal{F}$, and each element of
$\mathcal{F}$ is encoded by some $S_{i}$. We do not prescribe a specific way
to encode our graphs, but one option is to use our partite presentations from
[13], which is a generalisation of group presentations to arbitrary vertex-
transitive graphs. It would be already interesting to provide an effective
enumeration of the cubic, 2-ended, vertex-transitive graphs

A vertex-transitive graph $G\ $is said to be $n$-Cayley, if there is a
subgroup $\Gamma$ of $\mbox{Aut}(G)$ such that $\Gamma$ acts freely (i.e.
without fixing any point) on $V(G)$ and has $n$ orbits of vertices. Thus $G\
$is isomorphic to a Cayley graph if and only if it is 1-Cayley by Sabidussi’s
aforementioned theorem. If $n=2$ we say that $G\ $is _bi-Cayley_.

######  Problem 6.2.

Is every 2-ended, cubic, vertex-transitive graph Cayley or bi-Cayley?

Note that this is a relaxation of Watkins’ question that we negatively
answered with Theorem 1.4. Our case analysis in the proof of Corollary 1.2 is
helpful for this problem: in cases 1 & 3 it is not hard to obtain a positive
answer.

For graphs of degree higher than 3 we do not expect this to be true, as one
can obtain such a graph as the cartesian product of an arbitrary finite
vertex-transitive graph with the 2-way infinite path. But we expect that for
every $k\in\mathbb{N}$ there is $f(k)\in\mathbb{N}$ such that every
$k$-regular, 2-ended, vertex-transitive graph is $f(k)$-Cayley.

######  Problem 6.3.

Provided lower and upper bounds for $f(k)$.

Finally, it would be interesting to know whether Corollary 1.2 generalises to
graphs of arbitrary degree:

######  Problem 6.4.

Let $G\ =(V,E)$ be a 2-ended, $k$-regular, vertex-transitive graph. Must $G\
$be $k$-edge-colourable? Must $E$ decompose into $k$ perfect matchings?

Our harmonic function technique for Corollary 1.2 seems useful for this
general case.

## References

  * [1] B. Alspach, Y.-P. Liu, and C.-Q. Zhang.  Nowhere-Zero 4-Flows and Cayley Graphs on Solvable Groups.  SIAM J. Discrete Mathematics, 9(1):151–154, February 1996.
  * [2] I. Benjamini.  Instability of the Liouville property for quasi-isometric graphs and manifolds of polynomial volume growth.  J. Theor. Probab., 4(3):631–637, 1991.
  * [3] I. Benjamini, H. Duminil-Copin, G. Kozma, and A. Yadin.  Disorder, Entropy and Harmonic Functions.  The Annals of Probability, 43(5):2332–2373, 2015.
  * [4] A. Bou-Rabee, W. Cooperman, and P. Dario.  Rigidity of harmonic functions on the supercritical percolation cluster.  arXiv:2303.04736.
  * [5] S. G. Brick.  Quasi-isometries and ends of groups.  J. Pure Appl. Algebra, 86(1):23–33, 1993.
  * [6] S. Y. Cheng and S. T. Yau.  Differential equations on riemannian manifolds and their geometric applications.  Communications on Pure and Applied Mathematics, 28(3):333–354, 1975\.
  * [7] T. H. Colding and W. P. Minicozzi II.  Harmonic functions with polynomial growth.  Journal of Differential Geometry, 46(1):1–77, 1997.
  * [8] E. Csoka and G. Lippner.  Invariant random perfect matchings in Cayley graphs.  Groups, Geometry, and Dynamics, 11(1):211–243, 2017.
  * [9] H. Duminil-Copin and S. Smirnov.  The connective constant of the honeycomb lattice equals $\sqrt{2+\sqrt{2}}$.  Annals of mathematics, 175(3):1653–1665, 2012.
  * [10] A. Georgakopoulos.  The boundary of a square tiling of a graph coincides with the poisson boundary.  Invent. math., 203(3):773–821, 2016.
  * [11] A. Georgakopoulos.  Lecture Notes Markov Processes and Percolation Theory.  2021\.  Available at https://warwick.ac.uk/fac/sci/maths/people/staff/agelos_georgakopoulos/notesma3h2.pdf.
  * [12] A. Georgakopoulos and C. Panagiotis.  Convergence of square tilings to the Riemann map.  arXiv:1910.06886.
  * [13] A. Georgakopoulos and A. Wendland.  Presentations for Vertex Transitive Graphs.  J. Algebr. Comb., 55:795–826, 2022.
  * [14] A. Grigor’yan.  Analytic and geometric background of recurrence and non-explosion of the Brownian motion on Riemannian manifolds.  Bulletin Am. Math. Soc., 36(2):135–249, 1999.
  * [15] G. Grimmett and Z. Li.  Bounds on connective constants of regular graphs.  Combinatorica, 35(3):279–294, 2015.
  * [16] G. R. Grimmett and Z. Li.  Locality of connective constants.  Discrete Math., 341(12):3483–3497, 2018.
  * [17] G. R. Grimmett and Z. Li.  Cubic graphs and the golden mean.  Discrete Math., 343(1):111638, 2020.
  * [18] O. Gurel-Gurevich and A. Nachmias.  Recurrence of planar graph limits.  Annals of Mathematics, 177(2):761–781, 2013.
  * [19] B. Hua and J. Jost.  Polynomial growth harmonic functions on groups of polynomial volume growth.  Mathematische Zeitschrift, 280(1):551–567, 2015.
  * [20] B. Hua, J. Jost, and S. Liu.  Geometric analysis aspects of infinite semiplanar graphs with nonnegative curvature.  J. Reine Angew. Math., 2015(700):1–36, March 2015.
  * [21] B. Kleiner.  A new proof of Gromov’s theorem on groups of polynomial growth.  J. Amer. Math. Soc., 23:815–829, 2010.
  * [22] P. H. Leemann.  On subgroups and Schreier graphs of finitely generated groups. PhD Thesis.  Université de Genéve, 2016.
  * [23] Russell Lyons and Yuval Peres.  Probability on Trees and Networks.  Cambridge University Press, New York, 2016.  Available at http://pages.iu.edu/ rdlyons/.
  * [24] T. Lyons.  Instability of the Liouville property for quasi-isometric Riemannian manifolds and reversible Markov chains.  J. Differential Geom., 26(1):33–66, 1987.
  * [25] S. Markvorsen, S. McGuinness, and C. Thomassen.  Transient random walks on graphs and metric spaces with applications to hyperbolic surfaces.  Proc. London Math. Soc., 64:1–20, 1992.
  * [26] G. Sabidussi.  On a class of fixed-point-free graphs.  Proc. Am. Math. Soc., 9:800–804, 1958.
  * [27] Y. Shalom and T. Tao.  A Finitary Version of Gromov’s Polynomial Growth Theorem.  GAFA, 20(6):1502–1547, 2010.
  * [28] M. E. Watkins.  Vertex-transitive graphs that are not Cayley graphs.  In Cycles and rays (Montreal, PQ, 1987), volume 301 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 243–256. Kluwer Acad. Publ., Dordrecht, 1990.
  * [29] M. E. Watkins.  Edge-Transitive Strips.  Disc. Math., 95(1):359–372, 1991.
  * [30] Wolfgang Woess.  Random walks on infinite graphs and groups.  Cambridge University Press, 2002.
  * [31] S.-T. Yau.  Nonlinear Analysis in Geometry.  Enseign. Math., 33(2):109–158, 1987.