key: cord-0560024-2zhf0ivt
authors: Kamtue, Supanat
title: Bonnet-Myers sharp graphs of diameter three
date: 2020-05-14
journal: nan
DOI: nan
sha: c97ff56ed60d6c25f86733615e7b62aad9241515
doc_id: 560024
cord_uid: 2zhf0ivt

Regular graphs which are Bonnet-Myers sharp (in the sense of Ollivier Ricci curvature) and self-centered have been completely classified, and it is a natural question whether the condition of self-centeredness can be removed in the classification. We prove that this condition is indeed not necessary in the special case of Bonnet-Myers sharp graphs of diameter 3.

A classical theorem in Riemannian geometry is Bonnet-Myers theorem [5] , which states that a complete n-dimensional manifold M with positive Ricci curvature lower bound K = inf x∈M,v∈TxM |v|=1 Ric x (v) > 0 must be compact and its diameter has an upper bound diam(M ) ≤ π n − 1 K .

(1.1)

Moreover, Cheng's rigidity theorem [2] states that equality holds in (1.1) if and only if M is the n-dimensional round sphere.

In the setting of graphs, there is a discrete analogue of Bonnet-Myers theorem for Ollivier Ricci curvature (see, e.g., [4, 6] ) which states that for a graph G with positive curvature lower bound K = inf edges{x,y} κ(x, y) > 0, its diameter satisfies an upper bound

where κ is Ollivier Ricci curvature, introduced in [6] and modified in [4] . Regarding to an analogue of Cheng's rigidity result, the authors of [3] attempt to determine all regular graphs which attain equality in (1.2) . Such graphs are called Bonnet-Myers sharp.

The classification result given in [3] , however, is based on the additional assumption that graphs are self-centered, that is, every vertex has another corresponding vertex which is diametrically distance apart.

Theorem 1.1 ( [3] ). Self-centered Bonnet-Myers sharp graphs are precisely the following graphs:

1. hypercubes Q n , n ≥ 1;

2. cocktail party graphs CP (n), n ≥ 3;

3. the Johnson graphs J(2n, n), n ≥ 3;

4. even-dimensional demi-cubes Q 2n (2) , n ≥ 3;

and all Cartesian products G = G 1 × G 2 × · · · × G k where G i 's are from 1.-5. and satisfy

It was also shown in [3] that the self-centeredness assumption is not necessary for Bonnet-Myers sharp graphs of diameter 2 and diameter equal to the degree. In this paper, we prove the following theorem that this assumption can also be dropped in case of diameter 3. Indeed, this result is a consequence of particular local properties of 3-balls around a pole of general Bonnet-Myers sharp graphs of arbitrary diameter (see Section 5 and 6). We consider this approach as a starting point to potentially remove the self-centeredness condition for the general classification.

Theorem 1.2. Bonnet-Myers sharp graphs of diameter 3 are self-centered, and hence are precisely the following graphs:

1. the cube Q 3 ;

2. the Johnson graph J(6, 3);

3. the demi-cube Q 6 (2) ; 4. the Gosset graph.

The author would like to thank Thai Institute for the Promotion of Teaching Science and Technology for providing scholarship for his PhD study. He also express his deep gratitude to Prof. Shiping Liu from University of Science of Technology in China (USTC) for generously hosting the author's academic visit in 2019 where this project started to take place. Last but not least, the author are specially grateful to Prof. Norbert Peyerimhoff for all his helpful suggestions to the paper and moral support during the Covid-19 lockdown period.

All graphs G = (V, E), where V is the set of vertices and E is the set of edges, are assumed to be finite, simple (i.e., without multiple edges and loops) and connected. We write x ∼ y if there exists an edge {x, y} ∈ E between two different vertices x and y (and we may refer to this edge as x ∼ y). Furthermore, we use the convention x ≃ y to refer to "x ∼ y or x = y". For a set of vertices A ⊆ V , the induced subgraph Ind G (A) is the subgraph of G whose vertex set is A and whose edge set consists of all edges in G that have both endpoints in A. For any two vertices x and y, the combinatorial distance d(x, y) is the length (i.e., the number of edges) in a shortest path from x to y. Such paths of minimal length are also called geodesics from x to y. An interval [x, y] is the set of all vertices lying on geodesics from x to y, that is

By abuse of notation, we sometimes refer to [x, y] as the induced subgraphs

is the set of all neighbors of x, and we sometimes denote this set by N (x). The vertex degree of x is the number of neighbors of x, deg(x) := |N (x)|, and a graph G is called D-regular if all vertices have the same degree D. Furthermore, let # ∆ (x) and # ∆ (x, y) denote the numbers of triangles containing the vertex x, and containing the edge x ∼ y, respectively.

For x, y ∈ V , we also define

, which we respectively call the in-degree, spherical-degree, and out-degree of y with respect to the reference vertex x.

Ollivier Ricci curvature was originally defined in [6] to characterize positive Ricci curvature by the contraction property of L 1 -Wasserstein distance between two small balls around two different points. In this paper, we focus on the modified definition of the curvature in case of regular graphs, introduced in [4] and explicitly stated in [3, Definition 2.2] . Let us recall the following definitions which are relevant to this curvature notion.

Definition 2.1. Let G = (V, E) be a graph. Let µ 1 , µ 2 be two probability measures on V . The Wasserstein distance W 1 (µ 1 , µ 2 ) between µ 1 and µ 2 is defined as

where Π(µ 1 , µ 2 ) is the set of all transport plans π : V × V → [0, 1] satisfying the marginal constraints µ 1 (x) = y∈V π(x, y) and µ 2 (y) = x∈V π(x, y), and the cost of π is defined as cost(π) := x∈V y∈V d(x, y)π(x, y).

The transportation plan π in the above definition moves a mass distribution µ 1 into a mass distribution µ 2 , where π(x, y) represent the amount of mass moved from x to y, and W 1 (µ 1 , µ 2 ) is a measure for the minimal effort required for such transportation. If π attains the infimum in (2.1), we call it an optimal transport plan from µ 1 to µ 2 . 

where µ x is the uniform probability distribution on the 1-ball B 1 (x), defined by

Remark 2.1. Due to the fact that all individual masses in µ x and µ y are equal to 1 D+1 , there always exist an optimal transport plan π transporting from µ x to µ y without splitting masses. In other words, π is induced by a bijective optimal transport map T :

is the corresponding vertex in B 1 (y) such that π(v, T (v)) = 1 D+1 (and π(v, z) = 0 for all vertices z other than T (v)). Moreover, we can assume without loss of generality that we do not need to move masses from origin that already lie in the destination; in other words, T (v) = v for all v ∈ B 1 (x) ∩ B 1 (y) (see arguments in, e.g., [1, Lemma 4.1]).

A crucial theorem regarding this curvature notion is the Bonnet-Myers type diameter bound theorem, which is presented in [4, Theorem 4 .1] and stated as follows. 

The first result from [3, Theorem 5.8] gives the relation between in-degree, spherical-degree, and out-degree, with respect to a pole of a Bonnet-Myers sharp graph.

). Let G = (V, E) be a D-regular Bonnet-Myers sharp graph with diameter L. Let x 0 ∈ V be a pole and y ∈ S k (x 0 ). Then

where d − , d 0 , d + are in-degree, spherical-degree, and out-degree of y with respect to x 0 .

In particular, the above theorem implies the following result about degrees of vertices in the 1-sphere and the 2-sphere around a pole.

Corollary 3.2. Let G = (V, E) be a D-regular Bonnet-Myers sharp graph with diameter L. Let x 0 ∈ V be a pole and x 1 ∈ S 1 (x 0 ) and x 2 ∈ S 2 (x 0 ). Then

Proof of Corollary 3.2. The first two formulas follow from the fact that d − (x 1 ) = 1. Note also that (3.2) gives d + (

where the last formula follows immediately.

In the previous corollary, the spherical degree d 0

x 0 (x 1 ) = 2D L − 2 can also be interpreted as # ∆ (x 0 , x 1 ), the number of triangles containing the edge x 0 ∼ x 1 . In fact, the number of triangles containing any edge is bounded below by 2D L − 2 as stated in the following proposition. 

Proof of Proposition 3.3. For any D-regular graph, there is a relation between Ollivier Ricci curvature and the number of triangles containing an edge x ∼ y given in, e.g., [3, Proposition 2.7]:

Combined with the rigidity assumption (2.2) that inf

In this section, we recall a key concept of Bonnet-Myers sharp graphs, namely transport geodesics, introduced in [3] .

Consider a D-regular Bonnet-Myers sharp graph G = (V, E) with diameter L and a pole x 0 . Let us assume a full-length reference geodesic ℓ :

to µ x j satisfying the following properties:

Such a map T j is called a good optimal transport map. The existence of good maps T j is explained in Remark 2.1 (but they are not necessarily unique a priori).

Moreover, define maps T j :

and T 0 is the identity map on B 1 (x 0 ) by convention. These maps T j are also bijections.

An important aspect of Bonnet-Myers sharpness is stated in the following proposition, which is in the same spirit as [3, Propositions 7.1 and 7.2].

Given a full-length reference geodesic ℓ and maps T j and T j defined as above. Then for every z ∈ B 1 (x 0 ), the vertices x 0 , z, T 1 (z), T 2 (z), ..., T L (z), x L lie along a geodesic, that is,

The sequence of vertices x 0 , z, T 1 (z), T 2 (z), ..., T L (z), x L (which may contain repetitions) is called a transport geodesic along geodesic ℓ.

Proof of Proposition 4.1. The idea is to calculate the cost of transportation through the sequence of probability measures ½ x 0 , µ x 0 , µ x 1 , ..., µ x L , ½ x L . We define a positive real value

and we inspect these three terms separately. Firstly, observe that

is equal to the cost of T j (since it is an optimal map), which can be reformulated as

where the latter equality is due to labelling each v by T j−1 (z) since T j−1 is bijective.

Lastly, since T L is also bijective, we have

Combining (4.1), (4.2), (4.3) and applying triangle inequality yields

On the other hand, we have the rigidity assumption on (2.2) that inf x∼y κ(x, y) = 2 L , which implies

It follows that the triangle inequality in (4.4) holds with equality, which means

The above proposition has specific reinterpretations as stated in following two corollaries, which will be more conveniently used later in the paper. 

Proof of Corollary 4.2. This is an immediate consequence of Proposition 4.1 with v = T j−1 (z) by recalling that T j−1 is bijective. 

as they lie in the domain and codomain of the map T j , it is obvious that j − 2 ≤ m and n ≤ j

where the statements 1. and 2. immediately follow.

In words, if vertices of G are partitioned by layers S i (x 0 ) for 0 ≤ i ≤ L with respect to the pole x 0 , the above corollary asserts that the transport map T j always sends a vertex v to an outer layer (unless v is fixed by the map T j ).

Remark 4.4. Instead of assuming a full-length reference geodesic ℓ, let us start only with a geodesic

the set of all vertices of G. This immediately implies the uniqueness of the antipole x L . Moreover, the fact that v 2 ∈ [x 0 , x L ] implies that the geodesic x 0 ∼ x 1 ∼ x 2 can always be extended to a full-length geodesic

This geodesic extension allows us to conveniently discuss good optimal transport maps

without having to define a full-length reference geodesic or other maps T 3 , ..., T L .

In this section, we investigate local properties of a D-regular Bonnet-Myers sharp graph G = (V, E) with diameter L. These properties are local in the sense that they only concern the induced subgraph of B 3 (x 0 ) of a pole x 0 . To make it easier for readers to visualize, all of these properties are illustrated by diagrams. All diagrams display the induced subgraphs of those present vertices, that is, a pair of vertices are neighbors in G if and only if they are connected by an edge in the diagram. Moreover, vertices in S 1 (x 0 ), S 2 (x 0 ), and S 3 (x 0 ) are color-coded by red, green and blue, respectively.

The following two lemmas give information about intervals of length two; see Figure 1 .

Lemma 5.1. Let x 0 be a pole. For any x 1 ∈ S 1 (x 0 ) and x 2 ∈ S 2 (x 0 ) such that x 0 ∼ x 1 ∼ x 2 , there exists a unique x 1 ∈ S 1 (x 0 ) such that x 0 ∼ x 1 ∼ x 2 and x 1 ≃ x 1 . In other words, [x 0 , x 2 ] is a cocktail party graph (i.e., every vertex has exactly one antipole).

Furthermore, such x 1 can be realized as

are any good optimal transport maps.

(a) Illustration of Lemma 5.1

x 0

x 1 Proof of Lemma 5.1.

be any good optimal transport maps. Consider the vertex v :

. We firstly check that v is a candidate for

. Therefore, u = x 0 , which means v ′ = T 2 (u) = T 2 (x 0 ) is uniquely determined as the image of x 0 under the bijection T 2 .

We can also conclude from arguments in both paragraphs above that

be a good optimal transport map. Consider the vertex T 1 (x 1 ) ∈ B 1 (x 1 ). Firstly, note that T 1 (x 1 ) = x 1 due to property (P2) since

On the other hand, assume v ∈ S 2 (x 0 ) such that x 1 ∼ v ∼ x 1 . The preimage T −1 1 (v) must coincide with x 1 due to Lemma 5.1. Thus v = T 1 (x 1 ). This proves the uniqueness of x 2 . Proof of Lemma 5.3. To show the forward implication, assume for the sake of contradiction that y ∼ x 1 and y ∼ x 1 . Then y has the same properties as x 2 in Lemma 5.2, which contradicts to the uniqueness of such x 2 .

To prove the backward implication, we need some counting arguments. Consider a good optimal map B 1 (x 1 )

, and define the following sets:

as they contribute to the out-degree of x 1 .

For each v ∈ A 3 , we know v ∈ B 1 (x 2 ), so the image T 2 (v) = v by property (P2). Corollary 4.3 (with m = j = 2) then implies that T 2 (v) ∈ S 3 (x 0 ). Moreover, T 2 (v) ∈ B 1 (x 2 ) as the codomain of T 2 , which means T 2 (v) must be in S 3 (x 0 ) ∩ B 1 (x 2 ) = A 4 . Therefore,

which is the out-degree of x 2 . Combining formulas (5.1) and (5.2) gives

where the last equality comes from (3.5) .

Similarly (by interchanging the roles between x 1 and x 1 ), the cardinality of the set

. The forward implication shown earlier implies that A 2 ∩ A 2 = ∅. Therefore,

On the other hand, both A 2 and A 2 are subsets of A 5 , so

Therefore, all the inequalities above indeed hold with equality. Consequently, A 5 is partitioned into A 2 ⊔ A 2 . In other words, for every y ∈ S 2 (x 0 ) such that y ∼ x 2 , either y ∼ x 1 or y ∼ x 1 as desired.

Lemma 5.4. Let x 0 , x 1 , x 2 be defined as in Lemma 5.1 and let B 1 (x 1 )

be a good optimal transport map. Let v ∈ B 1 (x 1 ) and w ∈ B 1 (x 2 ) such that T 2 (v) = w. Then the following statements are true.

See Figures 3a, 3b, 3c for respective cases.

x 0

x The statement (b) is simply a reinterpretation of (a). For the statement (c), assume that v ∈ S 1 (x 0 ) and v ∼ x 2 . Since v ∈ B 1 (x 1 ) ∩ B 1 (x 2 ), we have w = T 2 (v) = v due to property (P2). Corollary 4.3 (with m = 1 and j = 2) further implies that w ∈ S 2 (x 0 ) or w ∈ S 3 (x 0 ). However, the latter case cannot happen due to (b), so w ∈ S 2 (x 0 ). Moreover, w ∼ x 1 ; otherwise, w ∈ B 1 (x 1 ) ∩ B 1 (x 2 ) would then imply by property (P2) that T 2 (v) = w = T 2 (w), which is impossible since w = v and T 2 is bijective. Recall also that w ∈ B 1 (x 2 ) but w = x 2 (since w ∼ x 1 ), so w ∼ x 2 . Finally, the fact that v ∼ w follows from Corollary 4.3 (with m = 1 and n = 2). Statement (c) is therefore proved.

Lemma 5.5. Let x 0 , x 1 , x 2 , x 1 be defined as in Lemma 5.1 and let u ∈ S 1 (x 0 ) and u ∈ {x 1 , x 1 }. Then u ∈ [x 0 , x 2 ] if and only if u is connected to both x 1 and x 1 .

x 0 For backward implication, assume u ∈ S 1 (x 0 ) such that x 1 ∼ u ∼ x 1 , and we would like to show that u ∼ x 2 . We will go a long way around for some counting arguments.

Fix an arbitrary vertex a ∈ S 1 (x 0 ). We define the following sets:

To count A 1 , there are t possibilities for vertex b, and for each b there are t − 1 possible vertices for c, where t :

Next, we would like to compare A 2 and A 4 . We firstly realize a one-to-one correspondence between 

We wish to prove the converse of (5.3), that is, to prove that the map (b, c) → (b, c ′ ) is surjective. The desired result u ∼ x 2 from the beginning of the proof will then follow by substituting a = x 1 , c = x 1 , c ′ = x 2 and b = u. To verify this surjection, it suffices to show that |A 4 | = |A 2 |.

For the cardinality of A 5 , we need to count the number of triangles △abc such that b ∈ S 1 (x 0 ) and a ∼ b. A vertex c could either come from S 1 (x 0 ) or S 2 (x 0 ), or c = x 0 . In case c ∈ S 1 (x 0 ), the number of △abc is exactly |A 3 |. In case c ∈ S 2 (x 0 ), the number of △abc is exactly |A 4 |. If c = x 0 , then there are t possibilities for such a vertex b. Overall, we have

On the other hand, since there are d 0 (a) = t possibilities for b ∈ S 1 (x 0 ) such that b ∼ a, and for each b, we know that # ∆ (a, b) ≥ t from Proposition 3.3. It means |A 5 | ≥ t 2 , which implies that the inequality (5.4) holds equality. Therefore |A 4 | = |A 2 | as desired.

The following two lemmas, which are inverse of each other, explain the situation when switching the roles between x 1 and x 1 ; see Figure 5 .

Lemma 5.6. Let x 0 , x 1 , x 1 , x 2 be as defined in Lemma 5.1. Let u ∈ S 1 (x 0 ) such that u ∼ x 1 but u ∼ x 2 , and let v ∈ S 2 (x 0 ) such that u ∼ v ∼ x 2 but v ∼ x 1 . Then x 0 , u, v, x 1 form a quadrilateral with u ∼ x 1 . In fact, for any such vertex u, there exists a unique such vertex v, namely v = T 2 (u) where B 1 (x 1 )

is a good optimal transport map.

Lemma 5.7. Let x 0 , x 1 , x 1 , x 2 be as defined in Lemma 5.1. Let u ∈ S 1 (x 0 ) such that u ∼ x 1 and u ∼ x 2 , and let v ∈ S 2 (x 0 ) such that u ∼ v ∼ x 2 and v ∼ x 1 . Then x 1 , u, v, x 2 form a quadrilateral with u ∼ x 2 and v ∼ x 1 .

x 0

Lemma 5.7 Proof of Lemma 5.6. Firstly, note that such a vertex v exists by considering v := T 2 (u) and recall Lemma 5.4(c).

Since v ∼ x 1 (by assumption), it is implied by Lemma 5.3 that v ∼ x 1 . Moreover, u ∼ x 1 (by assumption) implies that u ∼ x 1 (otherwise, u connected to both x 1 and x 1 would imply by Lemma 5.5 that u ∈ [x 0 , x 2 ], which contradicts to the assumption that u ∼ x 2 ). Therefore, we have a quadrilateral x 0 uvx 1 with u ∼ x 1 as desired. The uniqueness of v can be seen by Lemma 5.2 (with respect to x 0 , u, x 1 ).

Proof of Lemma 5.7. Consider the vertex u ′ := T −1 2 (v) ∈ B 1 (x 1 ) and we claim that u ′ and v satisfy

If we manage to prove these two claims and show that indeed u ′ = u, we will be done.

In claim 2, the fact that v ∈ S 2 (x 0 ) and v ∼ x 2 is actually a part of assumption on the vertex v. Moreover, the fact that v ∼ x 1 follows from Lemma 5.3 since v ∼ x 1 . We are left to prove in claim 2 that u ′ ∼ v.

Note that u ′ ∈ [x 0 , v] by Corollary 4.2. However, u ′ = x 0 (since T 2 (x 0 ) = x 1 by Lemma 5.1) and u ′ = v (since v ∈ B 1 (x 1 ) but u ′ ∈ B 1 (x 1 )). Therefore u ′ must lie inside the interior of [x 0 , v] (i.e., excluding endpoints x 0 , v). It means that x 0 ∼ u ′ ∼ v and u ′ ∈ S 1 (x 0 ). This finishes the proof of claim 1. Furthermore, we had

, which is false. This finishes the proof of claim 1. Now since u ′ and v satisfy all claimed properties, Lemma 5.6 (with u replaced by u ′ ) implies that x 0 , u ′ , v, x 1 form a quadrilateral with u ′ ∼ x 1 . Recall earlier that x 0 , u, v, x 1 also form a quadrilateral with u ∼ x 1 by assumption. In view of Lemma 5.1, the uniqueness of the antipole of x 1 in the cocktail party graph [x 0 , v] then implies u ′ = u as desired.

Continuing from the previous section, this section provides results concerning intervals of length three starting at a pole x 0 of a D-regular Bonnet-Myers sharp graph G = (V, E).

Let us start with x 0 , x 1 , x 1 , x 2 defined as in Lemma 5.1. As explained Remark 4.4, the extension of geodesics x 0 ∼ x 1 ∼ x 2 and x 0 ∼ x 1 ∼ x 2 allows us to simultaneously consider good optimal transport maps B 1 (x 0 )

→ w, and that u, v, w are all different. Then w ∈ S 3 (x 0 ), and u and x 2 are antipoles of each other with respect to the interval [x 0 , w]. In other words, u, x 2 ∈ [x 0 , w] and d(u, x 2 )=3.

Proof of theorem 6.1. Given that u ∈ S 1 (x 0 ) and u, v, w are all different, the following fact can be seen from Corollary 4.3.

(a) Summary of Fact 1 and Claim 1 and 2

x 0

Summary of Claim 7 Figure 6 : Summary of all the seven claims

Let v, w be the images u

We would like to verify the following seven claims.

Indirect proof for Claim 1:

1 (x 2 ) = x 1 by Lemma 5.1 (where the roles of x 1 and x 1 are interchanged and the map T 1 is replaced by T 1 ). This contradicts to u = x 1 , shown previously.

Indirect proof for Claim 2: If u ∼ x 1 , then v = T 1 (u) = u by property (P2) of the map T 1 . If u ∼ x 2 , then the fact that u ∼ x 1 implies that u = x 1 by the uniqueness in Lemma 5.1. This contradicts to Claim 1.

If v ∼ x 2 , then w = T 2 (v) = v by property (P2) of the map T 2 .

Fact 1 and Claim 1 and 2 altogether can be illustrated by Figure 6a .

Next, we will prove Claim 3 also by indirect proof. Assume for the sake of contradiction that u ≃ x 1 , i.e., u ∈ B 1 (x 1 ). The fact that u = x 1 from Claim 1 means u ∼ x 1 . Since u ∈ B 1 (x 1 ) lies in the domain of T 2 , we can define a vertex v ′ := T 2 (u). Now we have u ∈ B 1 (x 1 ) ∩ S 1 (x 0 ) and u ∼ x 2 (from Claim 2). We can then apply Lemma 5.4(c) (with the map T 2 replaced by T 2 and with vertices x 1 , v, w substituted by x 1 , u, v ′ , respectively) to conclude that v ′ ∈ S 2 (x 0 ) and v ′ ∼ x 1 and u ∼ v ′ ∼ x 2 . To visualize this, you may compare Figure 3c to Figure 7 (left diagram) with the mentioned substitution. Lemma 5.6 then implies that v ′ ∼ x 1 and v ′ ∼ x 2 , as illustrated in Figure 7 (which can be compared to Figure 5 where the roles of x 1 and x 1 are interchanged, and v is replaced by v ′ ). Now we know x 0 uv ′ x 1 is a quadrilateral without diagonal edges, and the same holds true for x 0 uvx 1 . However, Lemma 5.2 asserts that v ′ = v. This is impossible since v ′ ∼ x 2

x 0 Figure 7 : Situation assumed that u ≃ x 1 (for the sake of contradiction of Claim 3)

but v ∼ x 2 (from Claim 2). Therefore Claim 3 must be true: u ∼ x 1 .

Thus far, u ≃ x 1 from Claims 3 and 1. On the other hand, v = T 1 (u) ∈ B 1 (x 1 ) as the codomain of T 1 , so u = v. Corollary 4.3 then implies that v = T 1 (u) must lie in S 2 (x 0 ) and that u ∼ v, as stated in Claim 4.

Next, we prove Claim 5 indirectly: assume that v ≃ x 2 . The fact that from v = x 2 Claim 1 means v ∼ x 2 . Under this assumption, we have the following information as illustrated in the left diagram of Figure 8 : u ∈ S 1 (x 0 ), u ∼ x 1 and u ∼ x 2 (from Claim 2) and v ∈ S 2 (x 0 ) and u ∼ v ∼ x 2 (from Claim 4 and assumption) and v ∼ x 1 (as v is in the codomain of T 1 ). Lemma 5.7 then implies that x 1 , u, v, x 2 forms a quadrilateral (compare Figure 5 to Figure 8 , where v is replaced by v ′ ). This contradicts to the fact that u ∼ x 1 in Claim 2. Therefore, Claim 5 must be true.

x 0 Figure 8 : Situation assumed that v ∼ x 2 (for the sake of contradiction of Claim 5)

Thus far, v ≃ x 2 from Claims 5 and 1. Since v ∈ S 2 (x 0 ) from Claim 4, Corollary 4.3 implies that w = T 2 (v) must lie in S 3 (x 0 ) and that v ∼ w, which means Claim 6 is true. Note that Claim 7 is a combination of Claim 4 and 6, and it can be illustrated as in Figure  6b .

Now we are ready to prove the statement of the theorem. The fact that both u and x 2 lie in [x 0 , w] can be seen from x 0 ∼ u ∼ v ∼ w and x 0 ∼ x 1 ∼ x 2 ∼ w (where x 2 ∼ w comes from the fact that w = T 2 (v) ∈ B 1 (x 2 ) and w = x 2 ). We are left to prove that d(u, x 2 ) = 3.

Obviously, d(u, x 2 ) ≤ 3, and d(u, x 2 ) > 1 because u = x 2 (since u ∈ S 1 (x 0 ) but x 2 ∈ S 2 (x 0 )) and u ∼ x 2 from Claim 2. Assume for the sake of contradiction that d(u, x 2 ) = 2. Then there is a vertex b such that u ∼ b ∼ x 2 . Note that b is in either S 1 (x 0 ) or S 2 (x 0 ). The next paragraph argues that we can assume without loss of generality that b ∈ S 2 (x 0 ).

In case b ∈ S 1 (x 0 ), the geodesic extension of x 0 ∼ b ∼ x 2 (see Remark 4.4) allows us to consider good optimal transport maps B 1 (x 0 )

. Since u ∈ S 1 (x 0 ) and u ∼ b but u ∼ x 2 (from Claim 2), Lemma 5.4(c) implies that the vertex β := τ 2 (u) satisfies β ∈ S 2 (x 0 ) and u ∼ β ∼ x 2 (see Figure 9 compared to Figure 3(c) with vertices b, u, β replacing x 1 , v, w, respectively). Hence we can assume without loss of generality that b ∈ S 2 (x 0 ); otherwise, we may consider β instead b.

x 0 b u x 2 β τ 2 Figure 9 : If u ∼ b ∼ x 2 with b ∈ S 1 (x 0 ), then u ∼ β ∼ x 2 with β ∈ S 2 (x 0 ). Now we are able to assume b ∈ S 2 (x 0 ) and u ∼ b ∼ x 2 . Since b ∈ S 2 (x 0 ) and b ∼ x 2 , Lemma 5.3 implies that either b ∼ x 1 or b ∼ x 1 . If b ∼ x 1 , then x 0 , u, b, x 1 form a quadrilateral with u ∼ x 1 (from Claim 2). Since we also have a quadrilateral x 0 uvx 1 (see Figure 6 (a)), so the uniqueness by Lemma 5.2 guarantees that b = v, which is impossible since b ∼ x 2 but v ∼ x 2 (from Claim 2). By similar arguments, if b ∼ x 1 , then x 0 , u, b, x 1 form a quadrilateral with u ∼ x 1 (from Claim 3). By comparing this quadrilateral to

x 0 uvx 1 (see Figure 6 (b)), the uniqueness by Lemma 5.2 implies b = v, which is also impossible since b ∼ x 2 but v ∼ x 2 (from Claim 5).

In conclusion, d(u, x 2 ) = 3 as desired.

Another important theorem that follows from Theorem 6.1 is about the existence of antipoles with respect to intervals of length three. Theorem 6.2. Let x 0 be a pole and x 3 ∈ S 3 (x 0 ). Then for each vertex y ∈ [x 0 , x 3 ] such that y ∈ S 2 (x 0 ), there exists another vertex u ∈ [x 0 , x 3 ] such that d(u, y) = 3.

Proof of Theorem 6.2. For y ∈ [x 0 , x 3 ] such that y ∈ S 2 (x 0 ), we label y as x 2 . Choose an arbitrary vertex x 1 such that x 0 ∼ x 1 ∼ x 2 , and consider good optimal transport maps B 1 (x 0 )

. Let w := x 3 ∈ S 3 (x 0 ), and let vertices u, v be the preimages

→ w. Lemma 5.4(a) implies that v ∈ S 2 (x 0 ). We also know u ∈ B 1 (x 0 ) since it lies in the domain of T 1 . However, observe that u = x 0 ; otherwise, v = T 1 (u) = T 1 (x 0 ) = x 1 ∈ S 1 (x 0 ) by Lemma 5.1. Therefore, u ∈ S 1 (x 0 ), v ∈ S 2 (x 0 ), w ∈ S 3 (x 0 ), and we can apply Theorem 6.1 to conclude that the vertex u satisfies u ∈ [x 0 , x 3 ] and d(u, y) = 3. Corollary 6.3. Let G = (V, E) be a D-regular Bonnet-Myers sharp graph with diameter L = 3, then G is self-centered.

Proof of Corollary 6.3. Let x 0 and x 3 be antipoles of each other. We know from [3, Theorem 5.5] that [x 0 , x 3 ] = V , so any vertex y different from x 0 and x 3 must lie in S 2 (x 0 ) or S 2 (x 3 ). In either case, we can apply Theorem 6.2 (since both x 0 and x 3 are poles) and conclude that there exists a vertex u such that d(u, y) = 3.

Finally, our main result (Theorem 1.2) is an immediate consequence of Corollary 6.3 with the classification given in Theorem 1.1 in the introduction.

Ollivier-Ricci idleness functions of graphs

Eigenvalue comparison theorems and its geometric applications

Rigidity of the Bonnet-Myers inequality for graphs with respect to Ollivier Ricci curvature

Ricci curvature of graphs

Riemannian manifolds with positive mean curvature

Ricci curvature of Markov chains on metric spaces