graph_lly_curvature_pos_of_three
In a finite connected graph with exactly three vertices x, y, z, every edge xy has positive Lin–Lu–Yau curvature.
Statement
theorem graph_lly_curvature_pos_of_three {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y z : V) (hxy : G.Adj x y) (hzx : z ≠ x) (hzy : z ≠ y) (hall : ∀ w, w = x ∨ w = y ∨ w = z) : 0 < graph_lly_curvature G x y
- Source
- Helper for the refutation of OP-165 (arXiv:2610.10559, after Theorem 1.4).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- graph_lly_curvature_of_leafIf x is a leaf of a finite connected graph whose only neighbour is y, then κ_LLY(x, y) = 2/d_y.
- graph_lly_curvature_of_twinsIf x and y are adjacent and have the same neighbours apart from each other, then κ_LLY(x, y) = (d_x + 1)/d_x.
- graph_lly_curvature_commThe Lin–Lu–Yau curvature is symmetric: κ_LLY(x, y) = κ_LLY(y, x).
- graph_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
- Used by 1
- lly_positive_edge_connectivity_threshold_threec(3) = 0: every connected graph on 3 vertices has positive Lin–Lu–Yau curvature on every edge, whatever its edge-connectivity.
The proof, explained
In a connected graph with exactly three vertices x, y, z and an edge xy, the graph is either a triangle K₃ or a path P₃ of length 2. The proof splits into four cases depending on whether z is adjacent to x and whether z is adjacent to y. When z is adjacent to both, x and y are twin vertices, so the twin curvature formula gives (deg(x) + 1) / deg(x) > 0. When z is adjacent to exactly one of them, the non-adjacent vertex is a leaf, and the leaf formula gives 2 / deg(v) > 0. The case where z is adjacent to neither is impossible because connectivity guarantees that z has at least one neighbor.
The vertex z has a neighbor w in G, and x ≠ y.
Because G is connected, there exists a walk p from z to x. Since z ≠ x, this walk cannot be trivial (nil); its first step therefore provides a vertex w adjacent to z. In addition, since x and y are adjacent, x ≠ y by G.ne_of_adj.
uses
G.ne_of_adjobtain ⟨p⟩ := hG.preconnected z x obtain ⟨w, hzw⟩ : ∃ w, G.Adj z w := by cases p with | nil => exact absurd rfl hzx | cons h _ => exact ⟨_, h⟩ have hne : x ≠ y := G.ne_of_adj hxy
It suffices to consider the four cases of adjacency between z and {x, y}.
We perform a case split on whether x is adjacent to z and whether y is adjacent to z, yielding four possibilities: both adjacent, only x adjacent, only y adjacent, and neither adjacent.
by_cases ha : G.Adj x z <;> by_cases hb : G.Adj y z
If z is adjacent to both x and y, the curvature of xy is positive.
Any vertex other than x and y must be z by the three-vertex assumption. Since z is adjacent to both x and y, the vertices x and y have identical neighbors outside {x, y}; they are twins. By graph_lly_curvature_of_twins, the curvature equals (deg(x) + 1) / deg(x). Because x is adjacent to y, its degree is strictly positive by G.degree_pos_iff_exists_adj, so this ratio is strictly positive.
uses
graph_lly_curvature_of_twins,G.degree_pos_iff_exists_adj· rw [graph_lly_curvature_of_twins G hG x y hxy] · have : (0 : ℝ) < G.degree x := by exact_mod_cast (G.degree_pos_iff_exists_adj x).mpr ⟨y, hxy⟩ positivity · intro v hvx hvy rcases hall v with h | h | h · exact absurd h hvx · exact absurd h hvy · subst v; exact ⟨fun _ => hb, fun _ => ha⟩
If x is adjacent to z but y is not, the curvature of xy is positive.
In this case, y has no neighbor other than x: any neighbor must be x, y, or z, but self-loops are impossible by G.irrefl, and y is not adjacent to z by assumption. Thus y is a leaf. Using the symmetry of curvature (graph_lly_curvature_comm) and the leaf formula graph_lly_curvature_of_leaf, the curvature is 2 / deg(x). Since deg(x) > 0 by G.degree_pos_iff_exists_adj, this curvature is strictly positive.
uses
graph_lly_curvature_comm,graph_lly_curvature_of_leaf,G.degree_pos_iff_exists_adj,G.irrefl· rw [graph_lly_curvature_comm, graph_lly_curvature_of_leaf G hG y x hxy.symm] · have : (0 : ℝ) < G.degree x := by exact_mod_cast (G.degree_pos_iff_exists_adj x).mpr ⟨y, hxy⟩ positivity · intro v hv rcases hall v with h | h | h · exact h · subst v; exact absurd hv G.irrefl · subst v; exact absurd hv hb
If y is adjacent to z but x is not, the curvature of xy is positive.
Symmetrically, x has no neighbor other than y: any neighbor must be x, y, or z, but self-loops are ruled out by G.irrefl and x is not adjacent to z by assumption. Hence x is a leaf adjacent to y. By graph_lly_curvature_of_leaf, the curvature is 2 / deg(y). Since deg(y) > 0 by G.degree_pos_iff_exists_adj, the curvature is strictly positive.
uses
graph_lly_curvature_of_leaf,G.degree_pos_iff_exists_adj,G.irrefl· rw [graph_lly_curvature_of_leaf G hG x y hxy] · have : (0 : ℝ) < G.degree y := by exact_mod_cast (G.degree_pos_iff_exists_adj y).mpr ⟨x, hxy.symm⟩ positivity · intro v hv rcases hall v with h | h | h · subst v; exact absurd hv G.irrefl · exact h · subst v; exact absurd hv ha
The case where neither x nor y is adjacent to z is impossible.
By the initial connectedness step, z has some neighbor w. By the three-vertex assumption, w must be x, y, or z. But w cannot be x or y by the case assumptions (z is not adjacent to x or y), nor can w be z because simple graphs have no self-loops (G.irrefl). This contradiction rules out the final case.
uses
G.irrefl· exfalso rcases hall w with h | h | h · subst w; exact ha hzw.symm · subst w; exact hb hzw.symm · subst w; exact G.irrefl hzw
G.ne_of_adj- In a simple graph, adjacent vertices are distinct.
G.degree_pos_iff_exists_adj- A vertex in a graph has strictly positive degree if and only if it has at least one adjacent vertex.
G.irrefl- In a simple graph, adjacency is irreflexive: no vertex is adjacent to itself.
graph_lly_curvature_of_twins- If two adjacent vertices x and y have identical neighbors outside {x, y}, the Lin–Lu–Yau curvature of the edge xy is (deg(x) + 1) / deg(x).
graph_lly_curvature_comm- The Lin–Lu–Yau curvature of an edge is symmetric: the curvature of xy equals the curvature of yx.
graph_lly_curvature_of_leaf- If x is a leaf vertex whose only neighbor is y, the Lin–Lu–Yau curvature of the edge xy is 2 / deg(y).
- The hypothesis hne (x ≠ y) established on line 10 is never used in the subsequent proof.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem graph_lly_curvature_pos_of_three {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y z : V) (hxy : G.Adj x y) (hzx : z ≠ x) (hzy : z ≠ y) (hall : ∀ w, w = x ∨ w = y ∨ w = z) : 0 < graph_lly_curvature G x y := by obtain ⟨p⟩ := hG.preconnected z x obtain ⟨w, hzw⟩ : ∃ w, G.Adj z w := by cases p with | nil => exact absurd rfl hzx | cons h _ => exact ⟨_, h⟩ have hne : x ≠ y := G.ne_of_adj hxy by_cases ha : G.Adj x z <;> by_cases hb : G.Adj y z · rw [graph_lly_curvature_of_twins G hG x y hxy] · have : (0 : ℝ) < G.degree x := by exact_mod_cast (G.degree_pos_iff_exists_adj x).mpr ⟨y, hxy⟩ positivity · intro v hvx hvy rcases hall v with h | h | h · exact absurd h hvx · exact absurd h hvy · subst v; exact ⟨fun _ => hb, fun _ => ha⟩ · rw [graph_lly_curvature_comm, graph_lly_curvature_of_leaf G hG y x hxy.symm] · have : (0 : ℝ) < G.degree x := by exact_mod_cast (G.degree_pos_iff_exists_adj x).mpr ⟨y, hxy⟩ positivity · intro v hv rcases hall v with h | h | h · exact h · subst v; exact absurd hv G.irrefl · subst v; exact absurd hv hb · rw [graph_lly_curvature_of_leaf G hG x y hxy] · have : (0 : ℝ) < G.degree y := by exact_mod_cast (G.degree_pos_iff_exists_adj y).mpr ⟨x, hxy.symm⟩ positivity · intro v hv rcases hall v with h | h | h · subst v; exact absurd hv G.irrefl · exact h · subst v; exact absurd hv ha · exfalso rcases hall w with h | h | h · subst w; exact ha hzw.symm · subst w; exact hb hzw.symm · subst w; exact G.irrefl hzw