pith. sign in

arxiv: 2508.20950 · v2 · submitted 2025-08-28 · 🧮 math.CO · math.DG

Edge-connectivity and non-negative Lin-Lu-Yau curvature

Shiping Liu , Qing Xia This is my paper

Pith reviewed 2026-05-18 20:24 UTC · model grok-4.3

classification 🧮 math.CO math.DG
keywords edge-connectivityLin-Lu-Yau curvaturediscrete curvaturegraph theoryminimum degreefinite graphs
0
0 comments X

The pith

In finite connected graphs with non-negative Lin-Lu-Yau curvature, the edge-connectivity equals the minimum degree.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for any finite connected graph with non-negative Lin-Lu-Yau curvature on its edges, the edge-connectivity is exactly the minimum degree of the graph. This is because the curvature condition ensures that no smaller set of edges can disconnect the graph. The authors answer an open question from Chen, Liu and You by establishing this equality. They further classify the cases where the equality fails, showing that all such graphs must be infinite.

Core claim

By definition, the edge-connectivity of a connected graph is no larger than its minimum degree. We prove that the edge connectivity of a finite connected graph with non-negative Lin-Lu-Yau curvature is equal to its minimum degree. This answers an open question of Chen, Liu and You. We classify all connected graphs with non-negative Lin-Lu-Yau curvature and edge-connectivity smaller than their minimum degree; in particular, they are all infinite.

What carries the argument

Non-negative Lin-Lu-Yau curvature on edges, a discrete curvature condition that forces equality between edge-connectivity and minimum degree.

If this is right

  • Edge-connectivity reaches at least the minimum degree under the curvature condition.
  • Removing any set of edges smaller than the minimum degree leaves the finite graph connected.
  • The equality fails only for certain infinite graphs with the same curvature bound.
  • All exceptions to the equality under non-negative curvature are infinite.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Finiteness is essential for the equality, as the classification of infinite counterexamples demonstrates.
  • The link between discrete curvature and classical connectivity parameters may extend to related graph invariants.

Load-bearing premise

The graph must be finite.

What would settle it

A finite connected graph with non-negative Lin-Lu-Yau curvature on every edge but with edge-connectivity strictly less than its minimum degree.

Figures

Figures reproduced from arXiv: 2508.20950 by Qing Xia, Shiping Liu.

Figure 2
Figure 2. Figure 2: G1 4 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: G2 4 [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: insert K3 4 at a cut edge position of G4 [PITH_FULL_IMAGE:figures/full_fig_p004_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: insert a point at a cut edge position of G3 The graph sets we need in Theorem 1.4 are defined as follows: (1) ⟨K⟩(G4) = {G:G is obtained by performing the K-operation any number of times on G4}; (2) For all n ≥ 1, then ⟨P⟩(Gn) = {G:G is obtained by performing the P-operation any number of times on Gn}; (3) ⟨K, P⟩(G4) = {G:G is obtained by performing K-operation and P-operation any number of times on G4}. 4… view at source ↗
Figure 7
Figure 7. Figure 7: H1 n [PITH_FULL_IMAGE:figures/full_fig_p005_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: H3 n [PITH_FULL_IMAGE:figures/full_fig_p005_9.png] view at source ↗
Figure 11
Figure 11. Figure 11: Construct the struc￾ture of graph G1. Case 2: δ(G) = 3. step 1: Determine the structure of the bipartite graph H. Since δ(G) = 3, we have r = 2, and H is a star graph with three vertices or H = H1 2 . step 2: Establish the structures of G[A] and G[B]. According to Claim 5.5, Claim 5.7, Claim 5.8, and Lemma 5.1, we have (1) If H is a star graph, then G[A] = K1 and G[B] = K2; (2) If H = H1 , then G[A] = G[B… view at source ↗
Figure 12
Figure 12. Figure 12: An example of graph ⟨P⟩(G2). Case 3: δ(G) = 4. step 1: Determine the structure of the bipartite graph H. Since δ(G) = 4, r = 3 < 4. Thus H is a forest. According to Claim 5.7, we have H = H1 3 or H = H4 3 or H is a star graph. step 2: Establish the structures of G[A] and G[B]. According to Claim 5.5, Claim 5.7, Claim 5.8, and Lemma 5.1, we have (1) If H = H1 3 , then G[A] = G[B] = K3; (2) If H = H4 3 , th… view at source ↗
Figure 13
Figure 13. Figure 13: Construct the struc￾ture of graph G∗ 3 . Subcase 3:H is a star graph. Let A = {u}. By Claim 5.5, we have du = 6 and dy1 = dy2 = dy3 = δ(G) = 4. Set {z1, z2, z3} = S1(u) − B. Let X′ = X − A and Y ′ = Y ∪ A. Then E(X′ , Y ′ ) = {zi ∼ u|i = 1, 2, 3} is still a min-cut of graph G. Let H′ = (A′ ∪ B′ , E(X′ , Y ′ )), where A′ = {z1, z2, z3} and B′ = {u}. Then A′ ∪ B′ is a partition of V (H′ ). Therefore, we hav… view at source ↗
Figure 14
Figure 14. Figure 14: An example of graph ⟨P⟩(G3). Case 4: δ(G) = 5. step 1: Determine the structure of the bipartite graph H. Since δ(G) = 5, r = 4. According to Claim 5.7, we have H = K2,2 or H = Hi 4 where i ∈ {1, 2, 3} or H is a star graph with five vertices. step 2: Establish the structures of G[A] and G[B]. According to Claim 5.5, Claim 5.7, Claim 5.8, and Lemma 5.1, we have (1) If H = K2,2, then G[A] = G[B] = K2; (2) If… view at source ↗
Figure 15
Figure 15. Figure 15: Con￾struct the structure of graph G2 4 . Combining the Subcase 1, 2, 3, 4, along with the manner in which we define ⟨K, P⟩(G4), we conclude that the set of all graphs satisfying δ(G) = 5 is exactly the graph set ⟨K, P⟩(G4)∪{G1 4 , G2 4} we have defined [PITH_FULL_IMAGE:figures/full_fig_p052_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: An example of graph G ∈ ⟨K, P⟩(G4). Case 5: δ(G) ≥ 6. step 1: Determine the structure of the bipartite graph H. Since δ(G) ≥ 6, r ≥ 5. According to Claim 5.8, we have H = Hi r where i ∈ {1, 2, 3, 4} or H is a star graph with r + 1 vertices. step 2: Establish the structures of G[A] and G[B]. According to Claim 5.5, Claim 5.7, Claim 5.8, and Lemma 5.1, we have (1) If H = H2 r , then G[A] = K2 and G[B] = Kr;… view at source ↗
Figure 17
Figure 17. Figure 17: An example of graph G ∈ ⟨P⟩(G5). Finally, we complete the proof of Theorem 1.4. □ Acknowledgements This work is supported by the National Key R & D Program of China 2023YFA1010200 and the National Natural Science Foundation of China No. 12431004. We are very grateful to Kaizhe Chen for many useful discussions, especially for providing one of the sharp graphs, G∗ 3 . References [1] F. Bauer, J. Jost, S. Li… view at source ↗
read the original abstract

By definition, the edge-connectivity of a connected graph is no larger than its minimum degree. In this paper, we prove that the edge connectivity of a finite connected graph with non-negative Lin-Lu-Yau curvature is equal to its minimum degree. This answers an open question of Chen, Liu and You. Notice that our conclusion would be false if we did not require the graph to be finite. We actually classify all connected graphs with non-negative Lin-Lu-Yau curvature and edge-connectivity smaller than their minimum degree. In particular, they are all infinite.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves that for any finite connected graph with non-negative Lin-Lu-Yau curvature, the edge-connectivity equals the minimum degree. This resolves an open question of Chen, Liu and You. The authors further classify all connected graphs (necessarily infinite) with non-negative Lin-Lu-Yau curvature for which edge-connectivity is strictly smaller than the minimum degree.

Significance. If the result holds, it establishes a clean structural consequence of non-negative Lin-Lu-Yau curvature for finite graphs, analogous to connectivity results in Riemannian geometry. The proof derives a contradiction from the curvature definition whenever a cut of size less than the minimum degree exists, invoking finiteness to localize the cut or a minimum-degree vertex. The exhaustive classification of infinite counterexamples is a particular strength, as it confirms there are no finite exceptions and provides a complete dichotomy. The argument uses only the standard definition of the curvature and basic graph-theoretic notions, with no hidden regularity or bounded-degree assumptions.

minor comments (3)
  1. The abstract states the main theorem cleanly but could add one sentence indicating that the proof proceeds by contradiction using the curvature condition and finiteness.
  2. In the classification section, verify that the infinite counterexamples are presented with explicit constructions or references so that readers can reconstruct them without ambiguity.
  3. Ensure the citation to the open question of Chen, Liu and You includes the precise reference details and year.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of our manuscript, which correctly identifies the resolution of the open question posed by Chen, Liu and You, as well as the classification of infinite graphs where edge-connectivity is strictly less than the minimum degree. The recommendation for minor revision is noted, but the report does not specify any particular issues or changes.

Circularity Check

0 steps flagged

No circularity: direct proof from curvature definition and finiteness

full rationale

The manuscript proves edge-connectivity equals minimum degree for finite connected graphs with non-negative Lin-Lu-Yau curvature by deriving a contradiction from the curvature definition applied to any smaller edge cut, using finiteness only to localize a minimizing cut or minimum-degree vertex. It separately classifies all (infinite) counterexamples. No parameter fitting, no self-definitional loops, and the reference to the prior open question of Chen-Liu-You does not carry the proof load; the argument is self-contained against the standard curvature definition and basic graph theory. This is the normal non-circular outcome for a direct theorem.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard definition of Lin-Lu-Yau curvature for graphs, the assumption that the graph is finite and connected, and ordinary graph-theoretic facts such as Menger's theorem or cut properties. No free parameters or new invented entities are introduced.

axioms (2)
  • domain assumption The graph is finite and connected.
    Explicitly required in the statement; the paper notes the conclusion fails without finiteness.
  • domain assumption Lin-Lu-Yau curvature is defined and non-negative on every edge.
    Central hypothesis of the theorem.

pith-pipeline@v0.9.0 · 5611 in / 1121 out tokens · 29227 ms · 2026-05-18T20:24:49.450464+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Bauer, J

    F. Bauer, J. Jost, S. Liu, Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator, Math. Res. Lett. 19 (2012), no. 6, 1185-1205

    work page 2012

  2. [2]

    B. B. Bhattacharya, S. Mukherjee, Exact and asymptotic results on coarse Ricci curvature of graphs, Discrete Math. 338 (2015), no. 1, 23-42

    work page 2015

  3. [3]

    Bourne, D

    D. Bourne, D. Cushing, S. Liu, F. Münch, N. Peyerimhoff, Ollivier-Ricci idleness functions of graphs, SIAM J. Discrete Math. 32 (2018), no. 2, 1408-1424

    work page 2018

  4. [4]

    A. E. Brouwer and W. H. Haemers, Eigenvalues and perfect matchings, Linear Algebr. Appl., 395 (2005), pp. 155-162

    work page 2005

  5. [5]

    A. E. Brouwer and D. M. Menser, The connectivity for strongly regular graphs, European J. Combin. 6 (1985), no. 3, 215-216. 55

    work page 1985

  6. [6]

    K. Chen, J. H. Koolen, S. Liu, Edge-connectivity of graphs with non-negative Bakry-Émery curvature and amply regular graphs, arXiv: 2507.18120, 2025

    work page arXiv 2025

  7. [7]

    K. Chen, S. Liu, Z. You, Connectivity versus Lin-Lu-Yau curvature, arXiv: 2504.14352, 2025

    work page arXiv 2025

  8. [8]

    Cushing, S

    D. Cushing, S. Kamtue, J. Koolen, S. Liu, F. Münch, N. Peyerimhoff, Rigidity of the Bonnet-Myers inequality for graphs with respect to Ollivier Ricci curvature, Adv. Math. 369 (2020), 107188

    work page 2020

  9. [9]

    J. I. Hall, Locally Petersen graphs, J. Graph Theory 4 (1980), no. 2, 173-187

    work page 1980

  10. [10]

    P. Horn, A. Purcilly, A. Stevens, Graph curvature and local discrepancy, J. Graph Theory 108 (2025), no. 2, 337-360

    work page 2025

  11. [11]

    B. Hua, F. Münch, Every salami has two ends, J. Reine Angew. Math. 821 (2025), 291-321

    work page 2025

  12. [12]

    Huang, S

    X. Huang, S. Liu, Q. Xia, Bounding the diameter and eigenvalues of amply regular graphs via Lin-Lu-Yau curvature, Combinatorica 44 (2024), no. 6, 1177-1192

    work page 2024

  13. [13]

    Jost, Riemannian geometry and geometric analysis, Seventh edition, Universitext, Springer, Cham, 2017

    J. Jost, Riemannian geometry and geometric analysis, Seventh edition, Universitext, Springer, Cham, 2017

    work page 2017

  14. [14]

    J. Jost, S. Liu, Ollivier’s Ricci curvature, local clustering and curvature-dimension inequalities on graphs, Dis- crete Comput. Geom. 51 (2014), no. 2, 300-322

    work page 2014

  15. [15]

    Lin, S.-T

    Y. Lin, S.-T. Yau, Ricci curvature and eigenvalue estimate on locally finite graphs, Math. Res. Lett. 17 (2010), no. 2, 343-356

    work page 2010

  16. [16]

    Y. Lin, L. Lu, S.-T. Yau, Ricci curvature of graphs, Tohoku Math. J. 63 (2011), no. 4, 605-627

    work page 2011

  17. [17]

    L. Lu, Z. Wang, On the size of planar graphs with positive Lin-Lu-Yau Ricci curvature, arXiv: 2010.03716, 2020

    work page arXiv 2010

  18. [18]

    Mader, Minimalen-fach kantenzusammenhängende Graphen, Math

    W. Mader, Minimalen-fach kantenzusammenhängende Graphen, Math. Ann. 191 (1971), 21-28

    work page 1971

  19. [19]

    Münch, R

    F. Münch, R. Wojciechowski, Ollivier Ricci curvature for general graph Laplacians: Heat equation, Laplacian comparison, non-explosion and diameter bounds, Adv. Math. 356 (2019), 106759

    work page 2019

  20. [20]

    Najman and P

    L. Najman and P. Romon (Eds), Modern approaches to discrete curvature, Lecture Notes in Math., 2184, Springer, Cham, 2017

    work page 2017

  21. [21]

    Ollivier, Ricci curvature of Markov chains on metric spaces, J

    Y. Ollivier, Ricci curvature of Markov chains on metric spaces, J. Funct. Anal. 256 (2009), no. 3, 810-864

    work page 2009

  22. [22]

    Ollivier, C

    Y. Ollivier, C. Villani, A curved Brunn-Minkowski inequality on the discrete hypercube, or: what is the Ricci curvature of the discrete hypercube, SIAM J. Discrete Math. 26 (2012), no. 3, 983-996

    work page 2012

  23. [23]

    Salez, Sparse expanders have negative curvature, Geom

    J. Salez, Sparse expanders have negative curvature, Geom. Funct. Anal. 32 (2022), no. 6, 1486-1513

    work page 2022

  24. [24]

    J. D. H. Smith, Ricci curvature, circulants, and a matching condition, Discrete Math. 329 (2014), 88-98

    work page 2014

  25. [25]

    M. E. Watkins, Connectivity of transitive graphs, J. Combinatorial Theory 8 (1970), 23-29

    work page 1970

  26. [26]

    G. M. Weetman, A construction of locally homogeneous graphs, J. London Math. Soc. (2) 50 (1994), no. 1, 68-86

    work page 1994

  27. [27]

    G. M. Weetman, Diameter bounds for graph extensions, J. London Math. Soc. (2) 50 (1994), no. 2, 209-221. School of Mathematical Sciences, University of Science and Technology of China, 96 Jinzhai Road, Hefei 230026, Anhui Province, China Email address: spliu@ustc.edu.cn School of Mathematical Sciences, University of Science and Technology of China, 96 Jin...

    work page 1994