AFTD Auto-Formalizing Theoretical Domains

graph_lly_curvature_pos_of_three

theoremverified

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
Used by 1

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.

  1. 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.

    lines 5–10

    uses G.ne_of_adj

      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
  2. 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.

    line 11

      by_cases ha : G.Adj x z <;> by_cases hb : G.Adj y z
  3. 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.

    lines 12–20

    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⟩
  4. 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.

    lines 21–29

    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
  5. 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.

    lines 30–38

    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
  6. 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.

    lines 39–43

    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).

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

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
See it in the graphDiscuss this resultChallenge it