AFTD Auto-Formalizing Theoretical Domains

randic_index_nonneg

theoremverified

For any finite simple graph G on a finite vertex type V, its Randić index is non-negative: 0 ≤ randic_index G.

Statement

attribute [local instance] Classical.propDecidable in
theorem randic_index_nonneg {V : Type*} [Fintype V] (G : SimpleGraph V) :
  0 ≤ randic_index G
Source
arXiv:2611.03879 Lemma 15
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • randic_indexThe Randić index of a finite simple graph G is the sum over all edges e in G of 1 / Real.sqrt (degree(u) * degree(v)) where e is the…

Read back from the Lean

For every finite type $V$ and every simple graph $G$ on $V$, the Randić index of $G$ is greater than or equal to 0.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The Randić index of a graph is defined as the sum over all edges uv of 1 / √(deg(u) deg(v)). Since a finite sum of non-negative terms is non-negative, it suffices to check that each edge weight is non-negative. Every edge weight is the reciprocal of a real square root, which is non-negative because the square root function is everywhere non-negative.

  1. It suffices to show that each summand in the definition of the Randić index is non-negative.

    Unfolding the definition of the Randić index expresses it as the sum ∑_{e ∈ G.edgeFinset} w(e) over all edges of the graph. By `Finset.sum_nonneg`, a finite sum of real numbers is non-negative provided each term is non-negative, so it suffices to consider an arbitrary edge e of G.

    lines 5–7

    uses Finset.sum_nonneg

      unfold randic_index
      apply Finset.sum_nonneg
      intro e _
  2. For an edge with endpoints u, v ∈ V, the summand simplifies to 1 / √(deg(u) * deg(v)).

    Every edge e in the symmetric square Sym²(V) is an unordered pair s(u, v) for some vertices u, v ∈ V by `Sym2.inductionOn`. Simplifying the evaluation of the lifted symmetric function on s(u, v) using `Sym2.lift_mk` reduces the summand to 1 / √(deg(u) * deg(v)).

    lines 8–10

    uses Sym2.inductionOn, Sym2.lift_mk

      induction e using Sym2.inductionOn with
      | hf u v =>
        simp only [Sym2.lift_mk]
  3. The weight 1 / √(deg(u) * deg(v)) is non-negative.

    By `Real.sqrt_nonneg`, the square root √(deg(u) * deg(v)) is non-negative. Applying `one_div_nonneg.mpr`, the reciprocal of any non-negative real number is non-negative, which closes the goal.

    line 11

    uses one_div_nonneg.mpr, Real.sqrt_nonneg

        exact one_div_nonneg.mpr (Real.sqrt_nonneg _)
Finset.sum_nonneg
A finite sum is non-negative if every summand is non-negative.
Sym2.inductionOn
Every element of the symmetric square Sym²(α) can be represented as an unordered pair s(x, y) for some x, y ∈ α.
Sym2.lift_mk
The lift of a symmetric binary function to Sym² evaluated on an unordered pair s(a, b) equals the underlying function evaluated at a and b.
one_div_nonneg.mpr
The reciprocal 1 / x is non-negative if x is non-negative.
Real.sqrt_nonneg
The real square root √x is non-negative for every real number x.

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

attribute [local instance] Classical.propDecidable in/-- The Randić index of any finite simple graph is non-negative. -/theorem randic_index_nonneg {V : Type*} [Fintype V] (G : SimpleGraph V) :  0 ≤ randic_index G := by  unfold randic_index  apply Finset.sum_nonneg  intro e _  induction e using Sym2.inductionOn with  | hf u v =>    simp only [Sym2.lift_mk]    exact one_div_nonneg.mpr (Real.sqrt_nonneg _)
See it in the graphDiscuss this resultChallenge it