randic_index_nonneg
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.
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.
uses
Finset.sum_nonnegunfold randic_index apply Finset.sum_nonneg intro e _
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)).
uses
Sym2.inductionOn,Sym2.lift_mkinduction e using Sym2.inductionOn with | hf u v => simp only [Sym2.lift_mk]
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.
uses
one_div_nonneg.mpr,Real.sqrt_nonnegexact 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
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.
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 _)