Graphs with nonnegative Ricci curvature and maximum degree at most 3

Fengwen Han Fengwen, Han: School of Mathematical Sciences, Fudan University, Shanghai 200433, China [email protected] and Tao Wang Tao, Wang: School of Mathematical Sciences, Fudan University, Shanghai 200433, China [email protected]

Abstract.

In this paper, we classify graphs with nonnegative Lin-Lu-Yau-Ollivier Ricci curvature, maximum degree at most 3 and diameter at least 6.

1. Introduction

Ricci curvature is one of the most important geometric quantities in Riemannian geometry. For discrete settings, various definitions of Ricci curvature were developed over the past few decades. In this paper, we focus on Olliver Ricci curvature and its variations. The original Ollivier Ricci curvature was developed on metric spaces and Markov chains, which can be applied on normalized graphs; see [Oll09, Oll07]. In 2011, Lin-Lu-Yau [LLY11] modified Ollivier’s definition. This version was widely used in the research of normalized graphs. Münch and Wojciechowski [MW19] extended Lin-Lu-Yau’s definition to general weighted graphs. Bakry-Émery curvature is another important Ricci curvature on graphs, readers may refer to [Sch99, LY10] for more details.

There are significant geometric and analytic results for Riemannian manifolds with nonnegative Ricci curvature. As discrete analogs, graphs with nonnegative Ricci curvature are also worthy to study. A basic method is to explore their local geometric structures. Many papers on this subject were published recently. Cushing et al. [CKL⁺19] classified all 3-regular graphs with nonnegative Bakry-Émery curvature. They also classified all 3-regular graphs with nonnegative original Ollivier Ricci curvature. Under the setting of Lin-Lu-Yau-Ollivier Ricci curvature, there are many works on the classification of Ricci-flat graphs, i.e. graphs whose Ricci curvature vanishes on every edge; see [CKL⁺18, LLY14, CP18, HLYY18, BLY21].

It is interesting to study harmonic functions on graphs. For the continuous case, Yau [Yau75] showed that positive harmonic functions on a complete, noncompact Riemannian manifold with nonnegative Ricci curvature are constant, which is known as Liouville property of harmonic functions. For the discrete case, there are also some known results. Jost, Münch and Rose [JMR19] proved that bounded harmonic functions are constant under the nonnegative Lin-Lu-Yau-Ollivier Ricci curvature condition. We also refer to [Hua19, BHL⁺15, HLLY19] for Liouville properties under the other curvature conditions. However, the strong Liouville property of graphs with non-negative Lin-Lu-Yau-Ollivier Ricci curvature is still unknown. As an application of the main results, we prove that it is true for those graphs with maximum degree at most three.

Let $\mathcal{G}$ be the class of combinatorial graphs with following properties:

1) Lin-Lu-Yau-Ollivier Ricci curvatures on all edges of $G\in\mathcal{G}$ are nonnegative;

2) Degrees of all vertices of $G\in\mathcal{G}$ are at most 3;

3) Diameters of the graphs in $\mathcal{G}$ are at least 6.

The precise definition of $\mathcal{G}$ is given in section 2. We classify all graphs in $\mathcal{G}$ by the following two theorems.

Theorem 1.1.

Let $G\in\mathcal{G}$ be a finite graph. Then $G$ is isomorphic to a finite path, a simple cycle, a prism graph, a Möbius ladder, a particular graph as shown in Figure 1, or a quasi-ladder graph as shown in Figure 2.

Theorem 1.2.

Let $G\in\mathcal{G}$ be an infinite graph. Then $G$ is isomorphic to one of the following graphs.

Remark 1.3.

(1)

Theorem 1.1 and Theorem 1.2 also hold for normalized graphs; see Theorem 2.5.
(2)

For normalized graphs, if we change the nonegative Lin-Lu-Yau-Ollivier Ricci curvature constraint to nonnegative Ollivier Ricci curvature, we also get a classification; see Theorem 2.6.
(3)

It is well known that manifolds with nonnegative Ricci curvature satisfy Cheeger-Gromoll splitting theorem [CG72]. As a discrete analog, the splitting theorem also holds for Graphs in $\mathcal{G}$ , i.e. if a both-side infinite line is contained in $G\in\mathcal{G}$ , then $G$ is the Cartesian product of a line and a graph.

Bai, Lu and Yau [BLY21] classified all Ricci-flat graphs with maximum degree at most 4. Compared with our results, they require a more stringent curvature condition but relax the maximum degree condition from 3 to 4, which causes a huge increase in the complexity of the problem.

The proofs of the main results are shown in section 4. We give a sketch here. Let $P=v_{0}v_{1}\cdots v_{l}$ be a diameter of $G\in\mathcal{G}$ with $l\geq 6$ . The local structure along $P$ can be characterized in Lemma 3.1 , Lemma 3.3 and Lemma 3.4. Moreover, the subgraph induced by $P$ and its neighbors is a quasi-ladder. We divide $G$ into four parts as shown in Figure 4. If $L$ is connected to $R$ via $O$ , we will get a special cycle (we call it a geodesic cycle in this paper) by Lemma 4.1, and we prove $G$ has to be a cycle, a prism or a Möbius ladder by Lemma 4.2. If $L$ is not connected to $R$ via $O$ , then $O=\emptyset$ and $G$ is a quasi-ladder, otherwise we will find a longer geodesic path. For infinite graphs, the proof is similar. For graphs with small diameter, say $l=4\text{ or }5$ , the structures are more complicated. However, since the maximum degree is at most 3, graphs with nonnegative curvature and small diameter can be enumerated by computers, which we are not going to explore in this paper.

The paper is organized as follows: In next section, we introduce some notions on graphs and the definition of Ricci curvature. Section 3 gives the local structures of graph along a diameter, which serve as basic tools in the following discussions. In section 4, we prove the main results of this paper. In section 5, as an applications of the main results, we show that all positive harmonic functions on $G\in\mathcal{G}$ are constant.

2. Preliminaries

2.1. Basic notions

Throughout this paper, we always assume that $G(V,E)$ is an undirected, connected, locally finite, simple graph with vertex set $V$ and edge set $E$ . Let $|G|:=|V|$ be the number of vertices of the graph. For any vertices $u,v\in V$ , we call $v$ a neighbor of $u$ if $\{u,v\}\in E$ , denoted by $u\sim v$ . For notational simplicity, we write $uv$ for the unordered pair $\{u,v\}$ . For $A,B\subset V$ , let $E(A,B):=\{uv\in E:u\in A,v\in B\}$ . The degree of a vertex $v\in V$ is defined via $\deg(v):=\#\{u\in V:u\sim v\}$ . A graph $H(V^{\prime},E^{\prime})$ is called a subgraph of $G(V,E)$ if $V^{\prime}\subseteq V$ and $E^{\prime}\subseteq E$ . A subgraph $H$ is called an induced subgraph of $G$ if $E^{\prime}=\{\{u,v\}\in E:u,v\in V^{\prime}\}$ , and is denoted by $G(V^{\prime})$ . For $A,B\subseteq V^{\prime}$ , let $d_{H}(A,B):=\inf\{n:A\ni v_{0}\sim\cdots v_{n}\in B\}$ be the combinatorial distance between $A$ and $B$ in subgraph $H(V^{\prime},E^{\prime})$ . If $H=G$ , we omit the subscript, i.e. $d(A,B):=d_{G}(A,B)$ . If $A=\{u\}$ or $B=\{v\}$ is a single vertex subset, we will omit the braces, i.e. $d_{H}(u,v):=d_{H}(\{u\},\{v\})$ .

A walk $W$ of length $l$ is a sequence of vertices $v_{0},v_{1},\cdots,v_{l}$ such that $v_{i}\sim v_{i+1}$ for $i=0,1,\cdots,l-1$ . We write $W=v_{0}v_{1}\cdots v_{l}$ for short. If $v_{0}=v_{l}$ , we call it a closed walk. Moreover, a closed walk $W=v_{0}v_{1}\cdots v_{l}$ is called a cycle if $v_{i}\neq v_{j}$ for all $1\leq i,j\leq l$ . We also regard a cycle $C=v_{0}v_{1}\cdots v_{l}$ as a subgraph with vertex set $V(C)=\{v_{0},v_{1}\cdots v_{l-1}\}$ and edge set $E(C)=\{\{v_{i},v_{i+1}\}:i=0,1,\cdots l-1\}$ . A walk $W=v_{0}v_{1}\cdots v_{l}$ is called a path if $v_{i}\neq v_{j}$ for all $0\leq i,j\leq l$ . We also regard a path $P=v_{0}v_{1}\cdots v_{l}$ as a subgraph with vertex set $V(P)=\{v_{0},v_{1}\cdots v_{l}\}$ and edge set $E(P)=\{\{v_{i},v_{i+1}\}:i=0,1,\cdots l-1\}$ .

Let $H$ be a subgraph of $G$ . We say a path $P=v_{0}v_{1}\cdots v_{l}$ is geodesic in $H$ if $d_{H}(v_{0},v_{l})=l$ . It is easy to know that $P=v_{0}v_{1}\cdots v_{l}$ is a geodesic path of $H$ if and only if $d_{H}(v_{i},v_{j})=|i-j|$ for all $0\leq i,j\leq l$ . We say $H$ is a geodesic subgraph if all geodesic paths in $H$ are also geodesic paths in $G$ . It is not hard to verify that $H$ is a geodesic subgraph of $G$ if and only if $d_{H}(u,v)=d_{G}(u,v)$ for all $u,v\in H$ . A diameter path of $G$ is a longest geodesic path $P$ in $G$ . We let $\mathrm{diam}(G)$ denote the length of a diameter path in $G$ , i.e. $\mathrm{diam}(G)=\sup\{d(u,v):u,v\in V\}$ .

A graph $G(V,E)$ is called rooted at $p$ if a vertex $p\in V$ is specially appointed, denoted by $(G,p)$ . We define $r:V\to\mathbb{N}^{0}$ via $r(u)=d(p,u)$ . If $r(u)>0$ , there always exists a $v\sim u$ such that $r(v)=r(u)-1$ and a geodesic path $p\cdots vu$ with length equals to $r(u)$ . Given a geodesic path $P=v_{0}v_{1}\cdots v_{l}$ in $G$ , we always regard $G$ as a graph rooted at $v_{0}$ if not specified.

Let $G(V,E)$ be a graph with degree at most 3, $P=v_{0}v_{1}\cdots v_{l}$ be a geodesic path. For all $1\leq i\leq l-1$ , $v_{i}$ has at most one extra neighbor as $v_{i-1}$ and $v_{i+1}$ are two neighbors of $v_{i}$ . We define a state function $s:\{v_{i}:1\leq i\leq l-1\}\to\{2,3^{-},3^{0},3^{+}\}$ via

\displaystyle\begin{split}s(v_{i})=\begin{cases}2,\ \ \ \ \ \ \ \ \ &\text{if}\deg(v_{i})=2,\\ 3^{-},&\text{if }v_{i}\text{ has an extra neighbor }u_{i}\text{ and }r(u_{i})<r(v_{i}),\\ 3^{0},&\text{if }v_{i}\text{ has an extra neighbor }u_{i}\text{ and }r(u_{i})=r(v_{i}),\\ 3^{+},&\text{if }v_{i}\text{ has an extra neighbor }u_{i}\text{ and }r(u_{i})>r(v_{i}).\end{cases}\end{split}

As figures are quite important in the discussions of this paper, we explain the drawing style here. If not specified, a horizontal segment with vertices represents a geodesic path as shown in (a) of the following figure. If $v_{i}$ has an extra neighbor $u_{i}$ and $r(u_{i})<r(v_{i})$ , i.e. $s(v_{i})=3^{-}$ , we draw the figure as shown in (b) such that $u_{i}$ has the same abscissa with $v_{i-1}$ as $r(u_{i})=r(v_{i-1})$ . Figure (c) and (d) show the drawings when $r(u_{i})=r(v_{i})$ and $r(u_{i})>r(v_{i})$ respectively.

2.2. Ricci curvature on weighted graphs

Let

w:E\to\mathbb{(}0,\infty),\ \{x,y\}\mapsto w(x,y)=w(y,x)

be the edge weight function,

m:V\to(0,\infty),\ x\mapsto m(x)

be the vertex weight function. We call the quadruple $G=(V,E,m,w)$ a weighted graph. Unless otherwise specified, we always regard a graph $G(V,E)$ as a combinatorial graph, i.e. $w\equiv 1$ and $m\equiv 1$ . Our results also hold for normalized graphs, i.e. $w\equiv 1$ and $m(u)=\deg(u)$ for all $u\in V$ ; see Theorem 2.5.

We define the Laplacian $\Delta:\mathbb{R}^{V}\to\mathbb{R}^{V}$ via

\Delta f(u):=\frac{1}{m(u)}\sum_{v\sim u}w(u,v)(f(v)-f(u)).

A function $f$ on $G$ is called harmonic if $\Delta f\equiv 0$ .

For a weighted graph $G(V,E,w,m)$ , let $\mathrm{Deg}(u):=\sum_{v\sim u}\frac{w(u,v)}{m(u)}$ . We define a probability measure

\displaystyle\begin{split}\mu_{u}^{\varepsilon}(v)=\begin{cases}1-\varepsilon\mathrm{Deg}(u)\ \ \ \ \ \ \ &:v=u;\\ \varepsilon w(u,v)/m(u)\ &:\text{otherwise}.\end{cases}\end{split}

Particularly, for combinatorial graphs, we have

\displaystyle\begin{split}\mu_{u}^{\varepsilon}(v)=\begin{cases}1-\varepsilon\deg(u)\ \ \ \ \ \ \ &:v=u;\\ \varepsilon&:\text{otherwise}.\end{cases}\end{split}

For normalized graphs, we have

\displaystyle\begin{split}\mu_{u}^{\varepsilon}(v)=\begin{cases}1-\varepsilon\ \ \ \ \ \ \ \ \ \ &:v=u;\\ \varepsilon/\deg(u)\ &:\text{otherwise}.\end{cases}\end{split}

Definition 2.1.

(Wasserstein distance) Let $G(V,E)$ be a graph, $\mu$ and $\nu$ be two probability measures on $G$ . The Wasserstein distance $W(\mu,\nu)$ is given by

W(\mu,\nu):=\inf_{A}\sum_{u,v\in V}A(u,v)d(u,v),

where $A$ is a coupling between $\mu$ and $\nu$ , i.e. a mapping $A:V\times V\to[0,1]$ s.t.

\sum_{v\in V}A(u,v)=\mu(u)\text{ and }\sum_{u\in V}A(u,v)=\nu(v).

Definition 2.2.

For any vertices $u,v\in G(V,E,w,m)$ , the $\varepsilon$ -Ollivier-Ricci curvature $\kappa_{\varepsilon}(u,v)$ is defined via

\kappa_{\varepsilon}(u,v):=1-\frac{W(\mu_{u}^{\varepsilon},\mu_{v}^{\varepsilon})}{d(u,v)}.

Specifically, the Ollivier Ricci curvature on a normalized graph is defined via

\kappa^{O}(u,v):=\kappa_{1}(u,v).

The Lin-Lu-Yau-Ollivier Ricci curvature $\kappa(u,v)$ is defined via

\kappa(u,v):=\lim_{\varepsilon\to 0^{+}}\frac{1}{\varepsilon}\kappa_{\varepsilon}(u,v).

For fixed vertices $u,v\in E$ , it was shown in [BCL⁺18] that the function $\varepsilon\mapsto\kappa_{\varepsilon}(u,v)$ is concave and piecewise linear, so the limitation exists and $\kappa$ is well defined. There are also equivalent limit-free definitions via coupling function or Laplacian on graphs; see [BHLY20, MW19]. When we say Ricci curvature or curvature in the following, we always mean the Lin-Lu-Yau-Ollivier Ricci curvature defined above.

For combinatorial graphs, Münch and Wojciechowsk [MW19, Theorem 2.6] gave an easier way to calculate Ricci curvatures on edges as shown in the following theorem.

Theorem 2.3.

(Transport and combinatorial graphs) Let $G=(V,E)$ be a combinatorial graph and let $u\sim v$ be adjacent vertices. Let $B_{uv}:=B_{1}(u)\cap B_{1}(v)$ , $B_{u}^{v}:=B_{1}(u)\setminus B_{1}(v)$ and $B_{v}^{u}:=B_{1}(v)\setminus B_{1}(u)$ . Let $\Phi_{uv}:=\{\phi:D(\phi)\subseteq B_{u}^{v}\to R(\phi)\subseteq B_{v}^{u}\ :\phi\ bijective\}$ . For $\phi\in\Phi_{uv}$ write $D(\phi)^{c}:=B_{u}^{v}\setminus D(\phi)$ and $R(\phi)^{c}:=B_{v}^{u}\setminus R(\phi)$ . Then

\kappa(u,v)=\#B_{uv}-\inf_{\phi\in\Phi_{uv}}\left(\#D(\phi)^{c}+\#R(\phi)^{c}+\sum_{w\in D(\phi)}[d(w,\phi(w))-1]\right).

We always suppose $\#D(\phi)^{c}=0$ or $\#R(\phi)^{c}=0$ when applying Theorem 2.3. If $\phi$ is an optimal map such that $u\in D(\phi)^{c}$ and $v\in R(\phi)^{c}$ , we extend $\phi$ by adding an extra map $\phi(u)=v$ . It is easy to verify that the new $\phi$ is still an optimal map. So our hypothesis is fair. The following is a direct corollary of Theorem 2.3.

Corollary 2.4.

Let $G=(V,E)$ be a combinatorial graph and let $u\sim v$ be adjacent vertices. Let $N_{w}:=B_{1}(w)\setminus\{u,v\}$ be the set of extra neighbors of $w$ , $w\in\{u,v\}$ . If $|N_{u}|+|N_{v}|\geq 3$ and $d(N_{u},N_{v})\geq 3$ , we have $\kappa(u,v)<0$ .

Let $\kappa(G):=\inf_{\{u,v\}\in E}\kappa(u,v)$ be the Ricci curvature of $G$ and $\deg(G):=\sup_{u\in V}\deg(u)$ the maximum degree of $G$ . The class of graphs we will classify in this paper is defined by

\mathcal{G}:=\{G(V,E):\deg(G)\leq 3,\kappa(G)\geq 0,\mathrm{diam}(G)\geq 6\}.

Cushing et al. [CKL⁺19] provide a powerful online tool, the Graph Curvature Calculator, to calculate various of curvatures on graphs. Readers can find it on https://www.mas.ncl.ac.uk/graph-curvature/. By using this tool, it is convenient to check that the Ricci curvatures of graphs in Figure 1, 2 and 3 are nonnegative. We also use it to prove the following theorems.

Theorem 2.5.

Let $G=(V,E)$ be a graph with $\deg(G)\leq 3$ . Let $G_{C}$ be the combinatorial graph and $G_{N}$ be the normalized graph obtained by equipping $G$ with combinatorial weight and normalized weight respectively. Then $\kappa(G_{C})\geq 0$ if and only if $\kappa(G_{N})\geq 0$ .

Proof.

For any $uv\in E$ , let $\kappa_{C}(uv)$ be the curvature of $uv$ when $G$ is equipped with combinatorial weight and $\kappa_{N}(uv)$ be the curvature of $uv$ when $G$ is equipped with normalized weight. If $\deg(u)=1$ or $\deg(v)=1$ , we have $\kappa_{C}(uv)\geq 0$ and $\kappa_{N}(uv)\geq 0$ by a direct calculation. If $\deg(u)=\deg(v)$ , we have $\kappa_{C}(uv)=\deg(u)\cdot\kappa_{N}(uv)$ by the definition of Ricci curvature. So we only need to consider the case that $\deg(u)=2$ and $\deg(v)=3$ , i.e. $u$ has an extra neighbor $u^{\prime}$ , $v$ has two extra neighbors $v^{\prime}$ and $v^{\prime\prime}$ . Then $\kappa_{C}(uv)$ and $\kappa_{N}(uv)$ depend only on the distances $d(u^{\prime},v^{\prime})$ and $d(u^{\prime},v^{\prime\prime})$ . By a direct calculation, we have $\kappa_{C}(uv)<0$ $\Leftrightarrow$ $d(u^{\prime},v^{\prime})=d(u^{\prime},v^{\prime\prime})=3$ $\Leftrightarrow$ $\kappa_{N}(uv)<0$ . This completes the proof. ∎

It is noteworthy that Theorem 2.5 does not hold for graphs with maximum degree larger than 3. The minimum Ricci curvatures of the following graphs are 0, 0.5, -0.133 as normalized graphs and -1, -1, 0 as combinatorial graphs respectively. ¹¹1Graph (a) built by Bai-Lu-Yau [BLY21] is Ricci-flat as a normalized graph. Graphs (b) and (c) are pointed out to us by Florentin Münch.

Theorem 2.6.

Let $G$ be a normalized graph with nonnegative Ollivier Ricci curvature, maximum degree at most 3 and diameter at least 6. If $G$ is finite, then it is isometric to a finite path, a simple cycle, a prism graph, a Möbius ladder or a quasi-ladder as shown in the following figure. If $G$ is infinite, then it is isometric to (a), (b), (c), (d), (e), (f), (g) or (h) of Figure 3.

Proof.

For normalized graphs, $\kappa_{0}(u,v)\equiv 0$ for all $u,v\in V$ . If $\kappa^{O}(u,v)\geq 0$ , we always have $\kappa(u,v)\geq 0$ , as the function $\varepsilon\mapsto\kappa_{\varepsilon}(u,v)$ is concave and piecewise linear; see [BCL⁺18, Theorem 1.1]. This indicates that all normalized graphs with nonnegative Ollivier Ricci curvature are also graphs with nonnegative Lin-Lu-Yau-Ollivier Ricci curvature. We check the Ollivier Ricci curvatures of graphs in Figure 1, 2, 3 by using the Graph Curvature Calculator and get the result. ∎

3. The local structures

In this section, we study the local structure on a geodesic path of a graph $G\in\mathcal{G}$ .

Lemma 3.1.

Let $P=v_{0}\cdots v_{i}v_{i+1}v_{i+2}v_{i+3}\cdots v_{l}$ be a geodesic path of $G\in\mathcal{G}$ .

Case $(2,2)$ : If $(s(v_{i+1}),s(v_{i+2}))=(2,2)$ , then $G$ contains the following as a subgraph.

Case $(2,3^{-})$ : If $(s(v_{i+1}),s(v_{i+2}))=(2,3^{-})$ , then $G$ contains one of the followings as a subgraph.

Case $(2,3^{0})$ : If $(s(v_{i+1}),s(v_{i+2}))=(2,3^{0})$ , then $G$ contains the following as a subgraph.

Case $(2,3^{+})$ : The situation $(s(v_{i+1}),s(v_{i+2}))=(2,3^{+})$ can not exist.

Case $(3^{-},2)$ : The situation $(s(v_{i+1}),s(v_{i+2}))=(3^{-},2)$ can not exist.

Case $(3^{0},2)$ : If $(s(v_{i+1}),s(v_{i+2}))=(3^{0},2)$ , then $G$ contains the following as a subgraph.

Case $(3^{+},2)$ : If $(s(v_{i+1}),s(v_{i+2}))=(3^{+},2)$ , then $G$ contains one of the followings as a subgraph.

Case $(3^{-},3^{-})$ : If $(s(v_{i+1}),s(v_{i+2}))=(3^{-},3^{-})$ , then $G$ contains one of the followings as a subgraph.

Case $(3^{-},3^{0})$ : The situation $(s(v_{i+1}),s(v_{i+2}))=(3^{-},3^{0})$ can not exist.

Case $(3^{-},3^{+})$ : The situation $(s(v_{i+1}),s(v_{i+2}))=(3^{-},3^{+})$ can not exist.

Case $(3^{0},3^{-})$ : If $(s(v_{i+1}),s(v_{i+2}))=(3^{0},3^{-})$ , then $G$ contains one of the followings as a subgraph.

Case $(3^{0},3^{0})$ : If $(s(v_{i+1}),s(v_{i+2}))=(3^{0},3^{0})$ , then $G$ contains one of the followings as a subgraph.

Case $(3^{0},3^{+})$ : The situation $(s(v_{i+1}),s(v_{i+2}))=(3^{0},3^{+})$ can not exist.

Case $(3^{+},3^{-})$ : If $(s(v_{i+1}),s(v_{i+2}))=(3^{+},3^{-})$ , then $G$ contains one of the followings as a subgraph.

Case $(3^{+},3^{0})$ : If $(s(v_{i+1}),s(v_{i+2}))=(3^{+},3^{0})$ , then $G$ contains one of the followings as a subgraph.

Case $(3^{+},3^{+})$ : If $(s(v_{i+1}),s(v_{i+2}))=(3^{+},3^{+})$ , then $G$ contains one of the followings as a subgraph.

Proof.

We only show the proof of case $(2,3^{-})$ , proofs for other cases are similar. Without loss of generality, let $i=0$ . Then $G$ has a subgraph as shown in the following figure with $\deg(v_{1})=2$ .

By Theorem 2.3 we have

\kappa(v_{1},v_{2})=\#B_{v_{1}v_{2}}-\inf_{\phi\in\Phi_{v_{1}v_{2}}}(\#D(\phi)^{c}+\#R(\phi)^{c}+\sum_{w\in D(\phi)}[d(w,\phi(w))-1]),

where $B_{v_{1}v_{2}}=\{v_{1},v_{2}\}$ , $\Phi_{v_{1}v_{2}}=\{\text{all maps from $\{v_{0}\}$ to $\{v_{3},u_{2}\}$}\}$ , $\#D(\phi)^{c}=0$ , and $\#R(\phi)^{c}=1$ . Then we have

\begin{split}0&\leq\kappa(v_{1},v_{2})\\ &=2-\inf_{\phi(v_{0})\in\{v_{3},u_{2}\}}(0+1+d(v_{0},\phi(v_{0}))-1)\\ &=\max\{2-d(v_{0},v_{3}),2-d(v_{0},u_{2})\}.\end{split}

As $d(v_{0},v_{3})=3$ , we have $d(v_{0},u_{2})=1$ or $d(v_{0},u_{2})=2$ . If $d(v_{0},u_{2})=1$ , $G$ contain (a) of Figure 10 as a subgraph. If $d(v_{0},u_{2})=2$ , $G$ contains (b) or (c) of Figure 10 as a subgraph. This completes the proof. ∎

By applying case $(\cdot,3^{+})$ or case $(3^{-},\cdot)$ of Lemma 3.1 repeatedly, we get the following corollary.

Corollary 3.2.

Let $P=v_{0}v_{1}\cdots v_{l}$ be a geodesic path in $G\in\mathcal{G}$ , $l\geq 4$ .

1) If there exists a $i\in\{1,2,\cdots,l-1\}$ such that $s(v_{i})=3^{+}$ , then $s(v_{j})=3^{+}$ for all $1\leq j\leq i$ and $G$ has a subgraph (b) or (c) of the following figure.

2) If there exists a $i\in\{2,\cdots,l-1\}$ such that $s(v_{i})=3^{-}$ , then $s(v_{j})=3^{-}$ for all $i\leq j\leq l-1$ and $G$ has a subgraph (e) or (f) of the following figure.

As a supplement to Lemma 3.1, we explore the local structures on long geodesic paths in the following two lemmas,

Lemma 3.3.

Let $P=v_{0}\cdots v_{i}v_{i+1}v_{i+2}v_{i+3}\cdots v_{l}$ be a geodesic path with $l\geq 6$ . If $G$ contains (b) of Figure 16 as a subgraph, then $G$ is isometric to the particular graph (e) of Figure 1.

Proof.

If $i=2$ , $G$ contains a subgraph (a) of the following figure. By Corollary 3.2, $G$ contains a subgraph (b). By applying case $(3^{+},3^{0})$ of Lemma 3.1 on $v_{1}v_{2}v_{3}v_{4}$ , $G$ contains a subgraph (c). By applying case $(3^{+},3^{0})$ of Lemma 3.1 on $v_{1}u_{1}u_{3}u_{5}$ , $G$ contains a subgraph (d). Moreover, $\deg(v_{0})=\deg(v_{6})=1$ by Corollary 2.4. So $G$ is isometric to graph (d) of the following figure, which is isometric to (e) of Figure 1. If $i\neq 2$ , it is impossible to get a graph with nonnegative Ricci curvature by a similar argument. This proves the lemma.

∎

Lemma 3.4.

Let $P=v_{0}\cdots v_{i}v_{i+1}v_{i+2}v_{i+3}\cdots v_{l}$ be a geodesic path with $l\geq 6$ . Then none of the followings can be a subgraph of $G$ : (c) in Figure 10; (c) in Figure 13; (c), (d) and (e) in Figure 15; (c), (d), (e), (f) and (g) in Figure 17; (c), (d) and (e) in Figure 18.

Proof.

We only show (c) of Figure 13 can not be a subgraph of $G$ . Proofs for other cases are similar. We prove by contradiction. Suppose $i\leq 1$ , then $i+5\leq l$ and $G$ contains a subgraph (a) of the following figure with $\deg(v_{i+2})=2$ by Corollary 3.2. This is impossible as $\deg(u_{i+3})\leq 3$ and $u_{i+3}$ must has an extra neighbor $w_{i+3}$ with $r(w_{i+3})<r(u_{i+3})$ . Suppose $2\leq i\leq l-4$ . Then $G$ contains a subgraph (b) of the following figure with $\deg(v_{i+2})=2$ by Corollary 3.2. Applying case $(3^{0},3^{-})$ of Lemma 3.1 on $P^{\prime}=v_{0}\cdots w_{i+3}u_{i+3}v_{i+3}v_{i+4}\cdots$ , we get a contradiction. Suppose $i=l-3$ . Then $G$ contains a subgraph (c) of the following figure with $\deg(v_{l-1})=2$ by Corollary 3.2. We have $\kappa(u_{l},u_{l-2})<0$ by Theorem 2.3. This completes the proof.

∎

4. Classification of graphs

Let $G\in\mathcal{G}$ be a finite graph and $P=v_{0}v_{1}\cdots v_{l}$ be a diameter of $G$ . Then $P$ is a geodesic path. We explore all the available structures of $G$ separately by the following four cases.
Case (i): For all $1\leq i\leq l-1$ , $s(v_{i})=2$ . We discuss this case in Theorem 4.3.
Case (ii): There exists a $v_{i}$ such that $s(v_{i})=3^{0}$ . We discuss this case in Theorem 4.5.
Case (iii): There exists a $v_{i}$ such that $s(v_{i})=3^{-}$ . We discuss this case in Theorem 4.6.
Case (iv): There exists a $v_{i}$ such that $s(v_{i})=3^{+}$ . We discuss this case in Theorem 4.7.

We firstly introduce two lemmas.

Lemma 4.1.

Let $G(V,E)$ be a finite graph. Suppose $V=A\sqcup B\sqcup C_{1}\sqcup C_{2}$ satisfying:
(1) $E(A,B)=E(C_{1},C_{2})=\emptyset$ ;
(2) The induced subgraphs $G(C_{1})$ and $G(C_{2})$ are complete graphs, i.e. for all $u,v\in C_{i}$ , $u\sim v$ in $G(C_{i})$ , $i=1,2$ ;
(3) The induced subgraphs $G_{A}=G(A\sqcup C_{1}\sqcup C_{2})$ and $G_{B}=G(B\sqcup C_{1}\sqcup C_{2})$ are connected graphs.
Then $G$ contains a geodesic cycle $C$ with $|C|\geq d_{G_{A}}(C_{1},C_{2})+d_{G_{B}}(C_{1},C_{2})$ .

Proof.

Let $\mathcal{C}=$ { $W$ is a closed walk : $W=P_{1}P_{A}P_{2}P_{B}$ , where $P_{1}$ , $P_{2}$ , $P_{A}$ and $P_{B}$ are walks in $C_{1}$ , $C_{2}$ , $A$ and $B$ respectively}. Let $C\in\mathcal{C}$ with shortest length, then it is a cycle. Moreover, we can prove that $C$ is a geodesic cycle. Suppose not, there are $u,v\in C$ such that $d_{G}(u,v)<d_{C}(u,v)$ . We only prove the case that $u\in A$ and $v\in B$ , proofs for other cases are similar.

Let $P_{G}$ be a shortest walk between $u$ and $v$ in $G$ and $P_{C_{i}}$ be a shortest walk between $u$ and $v$ in $C$ crossing $C_{i}$ , $i=1,\ 2$ . Note that $P_{C_{1}}$ and $P_{C_{2}}$ are disjoint paths from $u$ to $v$ and $C$ is the union of them.

Next, we claim that $P_{G}$ has one of the following forms: $P_{A}P_{1}P_{A}^{\prime}P_{2}P_{B}$ , $P_{A}P_{1}P_{B}P_{2}P_{B}^{\prime}$ , $P_{A}P_{2}P_{A}^{\prime}P_{1}P_{B}$ , $P_{A}P_{2}P_{B}P_{1}P_{B}^{\prime}$ , $P_{A}P_{1}P_{B}$ or $P_{A}P_{2}P_{B}$ . In fact, it is easy to see that $P_{G}\cap C_{1}$ is connected in $P_{G}$ and $|P_{G}\cap C_{1}|\leq 2$ as $C_{1}$ is complete and $P_{G}$ is a shortest walk. The same conclusion holds for $P_{G}\cap C_{2}$ . So the claim holds.

Now, if $P_{G}=P_{A}P_{1}P_{A}^{\prime}P_{2}P_{B}$ , then $P_{G}$ and $P_{C_{1}}$ form a closed walk. By connecting $C_{1}$ part in $P_{G}$ and $C_{1}$ part in $P_{C_{1}}$ , we get a new closed walk $C^{\prime}\in\mathcal{C}$ with a shorter length. This contradicts to the fact that $C$ is a shortest walk. Proofs for other forms are similar. Then we proved $d_{G}(u,v)=d_{C}(u,v)$ for all $u,v\in C$ , i.e. $C$ is a geodesic cycle. The inequality $|C|\geq d_{G_{A}}(C_{1},C_{2})+d_{G_{B}}(C_{1},C_{2})$ is obtained directly from the construction of $C$ . ∎

Lemma 4.2.

Suppose $G\in\mathcal{G}$ contains a geodesic cycle $C$ with $|C|\geq 8$ , then $|C|\geq 11$ and $G$ must be a cycle, a prism graph or a Möbius ladder.

Proof.

Suppose $|C|=8$ . We assume that there exists a vertex, say $v_{0}$ , has an extra neighbor $u_{0}$ , otherwise $G=C$ . Note that every path $P$ in $C$ with $|P|\leq 5$ is geodesic in $G$ .

We claim that $G$ is a prism or Möbius ladder if $u_{0}\sim v_{2}$ . By applying local structure $(3^{-},\cdot)$ on $v_{1}v_{2}v_{3}v_{4}$ in $(G,v_{0})$ , we get that $G$ contains (a) or (b) of the following figure as a subgraph. By symmetric, $G$ has a subgraph (c) or (d) in the following figure. By doing this repeatedly, we get that $G$ has a subgraph (e). Finally we get a prism graph or a Möbius ladder.

We claim that $u_{0}$ is not a neighbor of $v_{1}$ . Suppose not, $G$ has a subgraph (a) of the following figure. Applying local structure $(3^{0},\cdot)$ on $v_{0}v_{1}v_{2}v_{3}$ in $(G,v_{0})$ , we know that $G$ has a subgraph (b) or (c) of the following figure. This is impossible by the symmetry of the geodesic cycle. So our claim is true.

The previous claim also shows $u_{0}\nsim v_{7}$ . By applying local structure $(3^{+},\cdot)$ on $v_{7}v_{0}v_{1}v_{2}$ in $(G,v_{7})$ , we know that $G$ has one of the following subgraphs.

By applying local structures on $C$ as we did previously, we get the following results. If $G$ has a subgraph (c) in Figure 27, then $G$ is isomorphic to (a) of Figure 28. Otherwise $G$ must be isometric to (b), (c) or (d) of the following figure if $G$ is not a prism graph or Möbius ladder.

Note that the diameters of all the possible graphs we get are less than 6, thus they are not elements of $\mathcal{G}$ . It follows that $|C|\neq 8$ . We also have $|C|\neq 9,10$ with similar arguments. When we do the previous steps on a geodesic cycle $C$ with $|C|\geq 11$ , the graphs with the same forms shown in Figure 28 contain edges with negative curvature. This indicates that $G$ must be a cycle, prism graph or Möbius ladder.

∎

Theorem 4.3.

Let $P=v_{0}v_{1}\cdots v_{l}$ be a diameter of $G\in\mathcal{G}$ with $l\geq 6$ . If for all $1\leq i\leq l-1$ , $s(v_{i})=2$ , then $G=P$ or isometric to a cycle.

Proof.

Let $G_{B}:=G(V\setminus\{v_{0},v_{1},\cdots,v_{l}\})$ . If $v_{0}$ is not connected to $v_{l}$ via $G_{B}$ , then $G=P$ , otherwise we will get a longer diameter. If $v_{0}$ is connected to $v_{l}$ via $G_{B}$ . By setting $C_{1}=\{v_{0}\}$ and $C_{2}=\{v_{l}\}$ and applying Lemma 4.1, we get a geodesic cycle $C$ with $|C|\geq 12$ . Then the theorem holds by Lemma 4.2. ∎

Lemma 4.4.

Let $P=v_{0}v_{1}\cdots v_{l}$ , $l\geq 6$ be a diameter of $G\in\mathcal{G}$ . If there exists $3\leq i\leq l-3$ such that $s(v_{i})=3^{0}$ , then $s(v_{j})=3^{0}$ for all $3\leq i\leq l-3$ , and $G$ contains a subgraph shown in the following figure.

Proof.

If $l=6$ , it is trivial. Suppose $l\geq 7$ and $i+1\leq l-3$ .

Firstly we prove $s(v_{i+1})=3^{0}$ . If $s(v_{i+1})=2$ , by applying local structure $(3^{0},2)$ on $v_{i-1}v_{i}v_{i+1}v_{i+2}$ and Corollary 3.2, we know that $G$ contains the following figure as a subgraph with $\deg(v_{i+1})=2$ . As $r(u_{i})>0$ , there is a vertex $w_{i}\sim u_{i}$ with $r(w_{i})<r(u_{i})$ . By applying local structure $(3^{0},3^{+})$ on $w_{i}u_{i}u_{i+2}u_{i+3}$ , we get a contradiction. If $s(v_{i+1})=3^{-}$ , by applying local structure $(3^{0},3^{-})$ on $v_{i-1}v_{i}v_{i+1}v_{i+2}$ and Corollary 3.2, we also get a contradiction. It follows that $s(v_{i+1})=3^{0}$ . By applying local structure $(3^{0},3^{0})$ on $v_{i-1}v_{i}v_{i+1}v_{i+2}$ , we have $u_{i}\sim u_{i+1}$ . If $i-1\geq 3$ , with the similar argument, we can also prove that $s(v_{i-1})=3^{0}$ .

By taking the previous steps repeatedly, we complete the proof. ∎

Theorem 4.5.

Let $P=v_{0}v_{1}\cdots v_{l}$ , $l\geq 6$ , be a diameter of $G\in\mathcal{G}$ . If there exists a $i\in\{1,2,\cdots,l-1\}$ such that $s(v_{i})=3^{0}$ , then $G$ is a quasi-ladder or isometric to the particular graph (d) in Figure 1.

Proof.

Let $k=\min\{i:s(v_{i})=3^{0},1\leq i\leq l-1\}$ . By Lemma 4.4, we have $k\in\{1,2,3,l-2,l-1\}$ .

Case (i): $k=1$ . $G$ contains (a) of the following figure as a subgraph. We claim that $s(v_{j})=3^{0}$ or $3^{-}$ for all $2\leq j\leq l-3$ . If $s(v_{2})=2$ , by applying local structure $(3^{0},2)$ on $v_{0}v_{1}v_{2}v_{3}$ , we have that $G$ has a subgraph (b) of the following figure. By applying local structure $(3^{0},3^{+})$ on $v_{0}u_{0}u_{3}u_{4}$ , we get a contradiction. If $s(v_{2})=3^{+}$ , we also get a contradiction by applying $(3^{0},3^{+})$ on $v_{0}v_{1}v_{2}v_{3}$ . So $s(v_{2})=3^{0}$ or $3^{-}$ .

If $s(v_{2})=3^{0}$ , we have $u_{0}\sim u_{2}$ as shown in (a) of the following figure by applying local structure $(3^{0},3^{0})$ on $v_{0}v_{1}v_{2}v_{3}$ . The previous argument tells us that $s(v_{3})\neq 2,3^{+}$ . It is not hard to verify that $s(v_{3})\neq 3^{-}$ neither. So $s(v_{3})=3^{0}$ and $u_{2}\sim u_{3}$ . By Lemma 4.4, $G$ has a subgraph (a) of the following figure. Moreover, $\deg(v_{0})=2$ , otherwise $v_{0}$ has an extra neighbor $w_{0}$ . Then $\deg(w_{0})=1$ by Corollary 2.4 and $d_{G}(w_{0},v_{l})=l+1$ , which is contrary to $\mathrm{diam}(G)=l$ . If $s(v_{2})=3^{-}$ , by Corollary 3.2 we have $s(v_{i})=3^{-}$ for $i\in\{2,3,\cdots,l-1\}$ and $G$ has a subgraph (b) of the following figure. Moreover, $\deg_{G}(u_{0})=2$ and $u_{0}v_{1}v_{2}\cdots v_{l}$ is also a diameter of $G$ . We can redraw (b) as shown in (c) of the following figure, which contains (a) as a subgraph. So we only need to consider the situation that $G$ contains a subgraph (a).

As we see, the left side of $G$ is fixed, we start to study the structure of the right side. If $\deg(v_{l-2})=2$ , $G$ contains a subgraph (a) of the following figure by applying local structure $(3^{0},2)$ on $v_{l-4}v_{l-3}v_{l-2}v_{l-1}$ . If $\deg(v_{l-2})=3$ , we have $s(v_{l-2})=3^{0}$ and $u_{l-3}\sim u_{l-2}$ . With similar arguments, we classify all possible structures of the right side of $G$ as shown in the following figure.

Case (ii): $k=2$ . By applying $(\cdot,3^{0})$ on $v_{0}v_{1}v_{2}v_{3}$ , $G$ contains a subgraph (a), (b) or (c) shown in the following figure. Obviously situation (c) is contained in (b) as $u_{0}u_{2}v_{2}v_{3}\cdots$ in (c) is also a diameter. We only need to consider the situation that $G$ has a subgraph (a) or (b). It is easy to verify that $\deg(v_{0})=1$ in (a) and $\deg(v_{0})=\deg(v_{1})=\deg(u_{0})=2$ in (b). So the left-hand side is fixed. The right-hand side of $G$ is the same with that in case (i).

Case (iii): $k=3$ . If $l\geq 7$ , the left side of $G$ is shown as following. The available structures of the right side are the same with that in case (i). If $l=6$ , $G$ has an additional available structure shown in (d) of Figure 1.

Case (iv): $k=l-2$ . It is easy to verify this case can not happen.

Case (v): $k=l-1$ . $G$ has a subgraph (a) or (b) shown in the following figure. As $v_{l}v_{l-1}\cdots v_{0}$ is also a diameter, graphs in this case have been discussed in the previous cases.

By previous discussions, we prove that $G$ must be a quasi-ladder graph with the following structures or isometric to the particular graph (d) in Figure 1.

∎

Theorem 4.6.

Let $P=v_{0}v_{1}\cdots v_{l}$ , $l\geq 6$ , be a diameter of $G\in\mathcal{G}$ . If for all $1\leq i\leq l-1,s(v_{i})\neq 3^{0},$ and there exists $v_{i}$ such that $s(v_{i})=3^{-}$ , then $G$ is a prism graph, a Möbius ladder or a quasi-ladder.

Proof.

Let $k=\min\{i:1\leq i\leq l-1\ ,\ s(v_{i})=3^{-}\}$ , then $k\geq 2$ .

Case (i): If $k=2$ , $G$ has a subgraph (a) of the following figure. By Corollary 3.2, $G$ has a subgraph (b) or (c) of the following figure. By switching $u_{0}$ and $v_{1}$ in (b), we get (b) is the same with (c). So we only consider the case that $G$ contains a subgraph (b).

Let $C_{1}=G(\{v_{0},v_{1}\})$ , $G_{A}=G(\{u_{0},u_{3},\cdots,u_{l-2},v_{2},v_{3}\cdots,v_{l-2}\})$ , $C_{2}=G(\{v_{l-1},u_{l-1}\})$ and $G_{B}=G(V\setminus\{u_{0},u_{3},\cdots,u_{l-1},v_{0},v_{1}\cdots,v_{l}\})$ . If $C_{1}$ is connected to $C_{2}$ via $G_{B}$ , we get a geodesic cycle $C$ with $|C|\geq 8$ by Lemma 4.1 and $G$ must be a prism graph or Möbius ladder by Lemma 4.2. In the following, we suppose that $C_{1}$ is not connected to $C_{2}$ via $G_{B}$ . With a similar argument in the proof of Theorem 4.5, the left side of $G$ has one of the following forms.

We start to deal with the right-hand side. If $\deg(u_{l-1})=2$ , we have $\deg(v_{l})=1$ by Corollary 2.4 and the structure of the right-hand side is (a) of the following figure. If $u_{l-1}$ has an extra neighbor $w_{l-1}$ , we have $r(u_{l-1})<r(w_{l-1})$ . Otherwise, $w_{l-1}$ has an extra neighbor $w^{\prime}$ and $\kappa(w^{\prime},w_{l-1})<0$ by Corollary 2.4. If $\deg(w_{l-1})=1$ , we have $\deg(v_{l})=1$ and the right-hand side structure is shown in (b) of the following figure. With similar arguments, we find all possible forms of the right side of $G$ as shown in the following figure.

Case (ii): $k=3$ . $G$ has a subgraph (a) of the following figure. The left side of $G$ must be (a) or (b) of the following figure and all possible forms of the right side have been shown in Figure 40.

Case (iii): $4\leq k\leq l-2$ . $G$ has a subgraph shown in the following figure which is the same with case (ii) by switching $u_{i-2}$ and $v_{i-1}$ , $4\leq i\leq k$ .

Case (iv): $j=l-1$ . $G$ contains a subgraph shown in the following figure which is the same with (a) of Figure 41 if $u_{l-2}\sim v_{l}$ , or (b) of Figure 41 if $u_{l-2}\nsim v_{l}$ as $P^{\prime}=v_{l}v_{l-1}\cdots v_{0}$ is also a diameter.

By previous discussions, we prove that if $G$ is not a prism graph or a Möbius ladder, then it has one of the following forms, which are isometric to graphs in Figure 45.

∎

Theorem 4.7.

Let $P=v_{0}v_{1}\cdots v_{l}$ , $l\geq 6$ , be a diameter of $G\in\mathcal{G}$ . Suppose that for all $1\leq i\leq l-1$ , $s(v_{i})\neq 3^{0},s(v_{i})\neq 3^{-}$ , and there exists $s(v_{i})=3^{+}$ , then $G$ is a prism graph, a Möbius ladder or a quasi-ladder.

Proof.

In fact we will prove that graphs considered in this theorem have been discussed in the previous theorems. Let $k=\max\{i:1\leq i\leq l-1,\ s(v_{i})=3^{+}\}$ , then $k=l-2$ or $l-1$ .

Case (i): $k=l-2$ . Then $\deg(v_{l-1})=2$ and $G$ has a subgraph shown in figure (a). By applying local structure $(3^{+},2)$ on $v_{l-3}v_{l-2}v_{l-1}v_{l}$ , we get that $G$ has a subgraph (b) or (c). We have discussed those graphs by changing $P=v_{0}v_{1}\cdots v_{l}$ to $P^{\prime}=v_{l}v_{l-1}\cdots v_{0}$ .

Case (ii): $k=l-1$ . $G$ contains one of the followings as a subgraph, which have been discussed in the previous theorems by changing $P=v_{0}v_{1}\cdots v_{l}$ to $P^{\prime}=v_{l}v_{l-1}\cdots v_{0}$ .

∎

Now, we give the proofs of Theorem 1.1 and 1.2.

Proof of Theorem 1.1.

By applying Theorem 4.3, 4.5, 4.6 and 4.7, we obtain the conclusion. ∎

Proof of Theorem 1.2.

As $G$ is an infinite graph, we can find an infinite geodesic path $P$ which is isometric to $\mathbb{Z}$ or $\mathbb{Z}^{+}$ . By applying the arguments used for finite graphs, we get the conclusion. ∎

5. Applications

In this section, as an application of the main results, we establish the following strong Liouville property.

Theorem 5.1.

Let $G\in\mathcal{G}$ be an infinite graph, then all positive harmonic functions on $G$ are constant.

Proof.

By Theorem 1.2, $G$ is a line, half line, infinite ladder or infinite quasi-ladder. As line and infinite ladder are finitely generated Cayley graphs of Abelian groups, all positive harmonic functions on them are constant; see [CD60]. Besides, Hua and Münch also proved all positive harmonic functions are constant on graphs with two ends and nonnegative Ricci curvature, which provides another proof for the strong Liouville property of line and infinite ladder; see [HM21, Theorem 5.9]. For a half line, there is a stronger conclusion. In fact all harmonic functions on a half line are constant. So, we only consider the quasi-ladder case.

Let $f$ be a positive harmonic function on $G$ . If $f$ is not a constant, there exist $i\geq 0$ , such that $f(x_{i})\neq f(y_{i})$ . Without loss of generality, we assume $i=0$ . By choosing suitable constants $a$ and $b$ such that $g:=af+b$ satisfies $g(x_{0})=1$ and $g(y_{0})=0$ , we get a harmonic function $g$ which is bounded from below or above.

For any $n\in\mathbb{Z}^{+}$ , we have

g(x_{n})=\frac{1}{3}(g(x_{n-1})+g(x_{n+1})+g(y_{n})),

g(y_{n})=\frac{1}{3}(g(y_{n-1})+g(y_{n+1})+g(x_{n})).

Let $z_{n}=g(x_{n})-g_{(}y_{n})$ , $h_{n}=g(x_{n})+g(y_{n})$ . We have $4z_{n}=z_{n-1}+z_{n+1}$ , $2h_{n}=h_{n-1}+h_{n+1}$ . On the one hand, it is easy to check that $h_{n}=O(n)$ . On the other hand, $z_{n}\geq z_{n-1}$ by the maximum principle. Thus $z_{n+1}\geq 3z_{n}$ , which means that $z_{n}\geq C\cdot 3^{n}$ for some constant $C>0$ . It follows that $g(y_{n})\to-\infty$ and $g(x_{n})\to+\infty$ as $n\to+\infty$ . We get a contradiction as $g$ is bounded from below or above. ∎

Acknowledgments

The authors are grateful to Prof. Bobo Hua for his guidance and support. The authors would also like to thank Florentin Münch and David Cushing for their helpful advice.

References

[BCL⁺18] D. P. Bourne, D. Cushing, S. Liu, F. Münch, and N. Peyerimhoff. Ollivier-Ricci idleness functions of graphs. SIAM J. Discrete Math., 32(2):1408–1424, 2018.
[BHL⁺15] Frank Bauer, Paul Horn, Yong Lin, Gabor Lippner, Dan Mangoubi, and Shing-Tung Yau. Li-Yau inequality on graphs. J. Differential Geom., 99(3):359–405, 2015.
[BHLY20] Shuliang Bai, An Huang, Linyuan Lu, and Shing-Tung Yau. On the sum of ricci-curvatures for weighted graphs. arXiv preprint arXiv:2001.01776, 2020.
[BLY21] Shuliang Bai, Linyuan Lu, and Shing-Tung Yau. Ricci-flat graphs with maximum degree at most 4. arXiv preprint arXiv:2103.00941, 2021.
[CD60] Gustave Choquet and Jacques Deny. Sur l’équation de convolution $\mu=\mu\ast\sigma$ . C. R. Acad. Sci. Paris, 250:799–801, 1960.
[CG72] Jeff Cheeger and Detlef Gromoll. The splitting theorem for manifolds of nonnegative Ricci curvature. J. Differential Geometry, 6:119–128, 1971/72.
[CKL⁺18] David Cushing, Riikka Kangaslampi, Yong Lin, Shiping Liu, Linyuan Lu, and Shing-Tung Yau. Ricci-flat cubic graphs with girth five. arXiv preprint arXiv:1802.02982, 2018.
[CKL⁺19] David Cushing, Riikka Kangaslampi, Valtteri Lipiäinen, Shiping Liu, and George W Stagg. The graph curvature calculator and the curvatures of cubic graphs. Experimental Mathematics, pages 1–13, 2019.
[CP18] Hee Je Cho and Seong-Hun Paeng. Classification of $\alpha$ -Ricci flat graphs with girth at least five. Discrete Math., 341(10):2894–2902, 2018.
[HLLY19] Paul Horn, Yong Lin, Shuang Liu, and Shing-Tung Yau. Volume doubling, Poincaré inequality and Gaussian heat kernel estimate for non-negatively curved graphs. J. Reine Angew. Math., 757:89–130, 2019.
[HLYY18] Weihua He, Jun Luo, Chao Yang, and Wei Yuan. Ricci-flat graphs with girth four. arXiv preprint arXiv:1807.07253, 2018.
[HM21] Bobo Hua and Florentin Münch. Every salami has two ends. arXiv preprint arXiv:2105.11887, 2021.
[Hua19] Bobo Hua. Liouville theorem for bounded harmonic functions on manifolds and graphs satisfying non-negative curvature dimension condition. Calc. Var. Partial Differential Equations, 58(2):Paper No. 42, 8, 2019.
[JMR19] Jürgen Jost, Florentin Münch, and Christian Rose. Liouville property and non-negative ollivier curvature on graphs. arXiv preprint arXiv:1903.10796, 2019.
[LLY11] Yong Lin, Linyuan Lu, and Shing-Tung Yau. Ricci curvature of graphs. Tohoku Math. J. (2), 63(4):605–627, 2011.
[LLY14] Yong Lin, Linyuan Lu, and S.-T. Yau. Ricci-flat graphs with girth at least five. Comm. Anal. Geom., 22(4):671–687, 2014.
[LY10] Yong Lin and Shing-Tung Yau. Ricci curvature and eigenvalue estimate on locally finite graphs. Math. Res. Lett., 17(2):343–356, 2010.
[MW19] Florentin Münch and Radosław K. Wojciechowski. Ollivier Ricci curvature for general graph Laplacians: heat equation, Laplacian comparison, non-explosion and diameter bounds. Adv. Math., 356:106759, 45, 2019.
[Oll07] Yann Ollivier. Ricci curvature of metric spaces. C. R. Math. Acad. Sci. Paris, 345(11):643–646, 2007.
[Oll09] Yann Ollivier. Ricci curvature of Markov chains on metric spaces. J. Funct. Anal., 256(3):810–864, 2009.
[Sch99] Michael Schmuckenschläger. Curvature of nonlocal Markov generators. In Convex geometric analysis (Berkeley, CA, 1996), volume 34 of Math. Sci. Res. Inst. Publ., pages 189–197. Cambridge Univ. Press, Cambridge, 1999.
[Yau75] Shing Tung Yau. Harmonic functions on complete Riemannian manifolds. Comm. Pure Appl. Math., 28:201–228, 1975.