AFTD Auto-Formalizing Theoretical Domains

op1012_randic_index_le_half_card

theoremverifiedformalization

For any finite simple graph G on a finite vertex type V, its Randić index is at most half the number of vertices: randic_index G ≤ (Fintype.card V : ℝ) / 2.

Statement

attribute [local instance] Classical.propDecidable in
theorem op1012_randic_index_le_half_card
    {V : Type*} [Fintype V] (G : SimpleGraph V) :
    randic_index G ≤ (Fintype.card V : ℝ) / 2
Formalizes
arXiv:2611.03879 Lemma 14
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 any finite type $V$ and any simple graph $G$ on $V$, the Randić index of $G$ is at most half the number of vertices in $V$ (that is, randic_index G ≤ (Fintype.card V : ℝ) / 2).

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 upper bound on the Randić index, $R(G) \le |V|/2$, is proved by applying the arithmetic-geometric mean inequality to each edge summand followed by double-counting via directed edges (darts). By AM-GM, each term $1/\sqrt{\deg u \deg v}$ is bounded above by $\frac{1}{2}(1/\deg u + 1/\deg v)$. Rewriting this edge sum as half the sum over all darts and applying dart reversal invariance, the sum simplifies to $\frac{1}{2} \sum_{d \in \text{Dart}(G)} 1/\deg(d.fst)$. Grouping darts by source vertex expresses this as $\frac{1}{2} \sum_{v \in V} \deg(v) \cdot (1/\deg v) \le |V|/2$, since each vertex term is at most 1.

  1. For any positive integers $a, b \ge 1$, $1 / \sqrt{ab} \le \frac{1}{2}(1/a + 1/b)$.

    Since $(1/\sqrt{a} - 1/\sqrt{b})^2 \ge 0$, expanding the square yields $(1/\sqrt{a})(1/\sqrt{b}) \le \frac{1}{2}((1/\sqrt{a})^2 + (1/\sqrt{b})^2)$. Simplifying the squares using $(1/\sqrt{a})^2 = 1/a$ and $(1/\sqrt{b})^2 = 1/b$, and factoring the square root of the product $\sqrt{ab} = \sqrt{a}\sqrt{b}$, establishes the inequality.

    lines 1–18

    uses sq_nonneg, div_pow, one_pow, Real.sq_sqrt, Real.sqrt_mul, one_div_mul_one_div

    open Finset
    
    private lemma op1012_randic_index_le_half_card_amgm_term (a b : ℕ) (ha : 1 ≤ a) (hb : 1 ≤ b) :
        1 / Real.sqrt ((a:ℝ) * (b:ℝ)) ≤ (1/2) * (1/(a:ℝ) + 1/(b:ℝ)) := by
      have ha' : (0:ℝ) < (a:ℝ) := by exact_mod_cast ha
      have hb' : (0:ℝ) < (b:ℝ) := by exact_mod_cast hb
      have key : (1/Real.sqrt (a:ℝ)) * (1/Real.sqrt (b:ℝ)) ≤
          (1/2) * ((1/Real.sqrt (a:ℝ))^2 + (1/Real.sqrt (b:ℝ))^2) := by
        nlinarith [sq_nonneg ((1:ℝ)/Real.sqrt (a:ℝ) - (1:ℝ)/Real.sqrt (b:ℝ))]
      have ha2 : (1/Real.sqrt (a:ℝ))^2 = 1/(a:ℝ) := by
        rw [div_pow, one_pow, Real.sq_sqrt ha'.le]
      have hb2 : (1/Real.sqrt (b:ℝ))^2 = 1/(b:ℝ) := by
        rw [div_pow, one_pow, Real.sq_sqrt hb'.le]
      have hmul : (1:ℝ)/Real.sqrt ((a:ℝ)*(b:ℝ)) = (1/Real.sqrt (a:ℝ)) * (1/Real.sqrt (b:ℝ)) := by
        rw [Real.sqrt_mul ha'.le, one_div_mul_one_div]
      rw [hmul, ← ha2, ← hb2]
      exact key
    
  2. For any edge $e = \{u, v\}$ and symmetric function $f$, the sum of $f(d.fst, d.snd)$ over all darts with underlying edge $e$ equals $2 f(u, v)$.

    An edge $e \in E(G)$ is an unordered pair $s(u, v)$ with $u$ adjacent to $v$. The fiber of darts projecting to $e$ consists of exactly two distinct darts, $d_0 = (u, v)$ and $d_0.\text{symm} = (v, u)$. The sum over this two-element fiber is $f(u, v) + f(v, u)$, which equals $2 f(u, v) = 2 \text{Sym2.lift } f(e)$ by the symmetry of $f$.

    lines 19–41

    uses Sym2.ind, SimpleGraph.mem_edgeSet, SimpleGraph.mem_edgeFinset, SimpleGraph.Dart.edge_fiber, Finset.sum_pair, SimpleGraph.Dart.symm_ne, Sym2.lift_mk

    attribute [local instance] Classical.propDecidable in
    private lemma op1012_randic_index_le_half_card_two_mul_edge_sum {V : Type*} [Fintype V]
        (G : SimpleGraph V) (f : V → V → ℝ) (hf : ∀ a b, f a b = f b a) :
        2 * ∑ e ∈ G.edgeFinset, Sym2.lift ⟨f, hf⟩ e = ∑ d : G.Dart, f d.fst d.snd := by
      classical
      have hinner : ∀ e ∈ G.edgeFinset,
          ∑ d ∈ (univ : Finset G.Dart).filter (fun d => d.edge = e), f d.fst d.snd
            = 2 * Sym2.lift ⟨f, hf⟩ e := by
        intro e
        induction e using Sym2.ind with
        | h u v =>
          intro he
          have hadde : G.Adj u v := by
            rw [← SimpleGraph.mem_edgeSet]
            exact (SimpleGraph.mem_edgeFinset).1 he
          let d0 : G.Dart := ⟨(u, v), hadde⟩
          have hfilter : (univ : Finset G.Dart).filter (fun d => d.edge = s(u, v)) = {d0, d0.symm} :=
            SimpleGraph.Dart.edge_fiber d0
          rw [hfilter, Finset.sum_pair (SimpleGraph.Dart.symm_ne d0).symm]
          rw [Sym2.lift_mk]
          show f u v + f v u = 2 * f u v
          rw [hf v u]
          ring
  3. Twice the sum of a symmetric function over all edges equals the sum of the function over all darts: $2 \sum_{e \in E} f(e) = \sum_{d \in \text{Dart}(G)} f(d.fst, d.snd)$.

    Distributing the factor of 2 into the sum over edges and substituting the fiber sum for each edge gives a double sum over edges and darts in each edge fiber. Exchanging the order of summation and using the fact that every dart belongs to a unique edge in the graph simplifies the expression to the total sum over all darts of $G$.

    lines 42–55

    uses Finset.mul_sum, Finset.sum_congr, Finset.sum_filter, Finset.sum_comm, Finset.sum_ite_eq, SimpleGraph.Dart.edge_mem

      calc 2 * ∑ e ∈ G.edgeFinset, Sym2.lift ⟨f, hf⟩ e
          = ∑ e ∈ G.edgeFinset, 2 * Sym2.lift ⟨f, hf⟩ e := by rw [Finset.mul_sum]
        _ = ∑ e ∈ G.edgeFinset, ∑ d ∈ (univ : Finset G.Dart).filter (fun d => d.edge = e),
              f d.fst d.snd := by
            refine Finset.sum_congr rfl ?_
            intro e he
            rw [hinner e he]
        _ = ∑ d : G.Dart, f d.fst d.snd := by
            rw [Finset.sum_congr rfl (fun e he => Finset.sum_filter _ _), Finset.sum_comm]
            refine Finset.sum_congr rfl ?_
            intro d _
            rw [Finset.sum_ite_eq]
            simp [SimpleGraph.Dart.edge_mem]
    
  4. For any vertex function $a : V \to \mathbb{R}$, the sum of $a(d.fst)$ over all darts equals the degree-weighted sum over vertices: $\sum_{d \in \text{Dart}(G)} a(d.fst) = \sum_{v \in V} \deg(v) a(v)$.

    Darts bijectively correspond to pairs $(v, w)$ where $v \in V$ and $w \in N(v)$ is a neighbor of $v$. Reindexing the sum over darts as a sum over $v \in V$ followed by a sum over $w \in N(v)$, the summand $a(v)$ is independent of $w$. The inner sum therefore evaluates to $|N(v)| \cdot a(v) = \deg(v) \cdot a(v)$.

    lines 56–77

    uses Fintype.sum_equiv, Fintype.sum_sigma, Finset.sum_congr, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, SimpleGraph.card_neighborSet_eq_degree

    attribute [local instance] Classical.propDecidable in
    private lemma op1012_randic_index_le_half_card_sum_dart_fst {V : Type*} [Fintype V]
        (G : SimpleGraph V) (a : V → ℝ) :
        ∑ d : G.Dart, a d.fst = ∑ v, (G.degree v : ℝ) * a v := by
      classical
      let ee : G.Dart ≃ Σ v : V, G.neighborSet v :=
        { toFun := fun d => ⟨d.fst, ⟨d.snd, d.adj⟩⟩
          invFun := fun s => ⟨(s.1, s.2.1), s.2.2⟩
          left_inv := by intro d; rfl
          right_inv := by intro s; rfl }
      rw [Fintype.sum_equiv ee (fun d : G.Dart => a d.fst) (fun s => a s.1) (by intro d; rfl)]
      rw [Fintype.sum_sigma]
      refine Finset.sum_congr rfl ?_
      intro v _
      have hc : (∑ y : G.neighborSet v, a ((⟨v, y⟩ : Σ w : V, G.neighborSet w).fst))
          = ∑ _y : G.neighborSet v, a v :=
        Finset.sum_congr rfl (fun y _ => rfl)
      rw [hc]
      rw [show (∑ _y : G.neighborSet v, a v) = (Fintype.card (G.neighborSet v) : ℝ) * a v from by
        simp [Finset.sum_const, Finset.card_univ, nsmul_eq_mul]]
      rw [SimpleGraph.card_neighborSet_eq_degree]
    
  5. Summing a vertex function evaluated at the target of each dart equals summing it at the source: $\sum_{d \in \text{Dart}(G)} a(d.snd) = \sum_{d \in \text{Dart}(G)} a(d.fst)$.

    Dart reversal $d \mapsto d.\text{symm}$ is a bijection on the set of darts that interchanges the source and target endpoints, $(d.\text{symm}).fst = d.snd$. Summing $a(d.fst)$ after composing with this involution preserves the sum and yields $\sum_d a(d.snd)$.

    lines 78–90

    uses SimpleGraph.Dart.symm, SimpleGraph.Dart.symm_symm, Equiv.sum_comp

    attribute [local instance] Classical.propDecidable in
    private lemma op1012_randic_index_le_half_card_sum_dart_snd {V : Type*} [Fintype V]
        (G : SimpleGraph V) (a : V → ℝ) :
        ∑ d : G.Dart, a d.snd = ∑ d : G.Dart, a d.fst := by
      classical
      let σ : G.Dart ≃ G.Dart :=
        { toFun := SimpleGraph.Dart.symm
          invFun := SimpleGraph.Dart.symm
          left_inv := fun d => SimpleGraph.Dart.symm_symm d
          right_inv := fun d => SimpleGraph.Dart.symm_symm d }
      have h := Equiv.sum_comp σ (fun d : G.Dart => a d.fst)
      simpa [σ] using h
    
  6. The Randić index of $G$ is bounded above by the edge sum of the arithmetic mean of reciprocal degrees: $\sum_{e \in E} \frac{1}{\sqrt{\deg u \deg v}} \le \sum_{e \in E} \frac{1}{2}(\frac{1}{\deg u} + \frac{1}{\deg v})$.

    By definition, the Randić index is the sum over edges $\{u, v\}$ of $1/\sqrt{\deg u \deg v}$. For any edge $\{u, v\} \in E(G)$, both vertices have degree at least 1 since they are adjacent. Applying the AM-GM lemma to each edge establishes that $1/\sqrt{\deg u \deg v} \le \frac{1}{2}(1/\deg u + 1/\deg v)$, and summing this over all edges yields the bound.

    lines 91–117

    uses mul_comm, add_comm, Finset.sum_le_sum, Sym2.ind, Sym2.lift_mk, SimpleGraph.mem_edgeSet, SimpleGraph.mem_edgeFinset, SimpleGraph.degree_pos_iff_exists_adj, op1012_randic_index_le_half_card_amgm_term

    attribute [local instance] Classical.propDecidable in
    /-- Upper bound on the Randić index: for any finite simple graph G, R(G) ≤ |V| / 2. -/
    theorem op1012_randic_index_le_half_card
        {V : Type*} [Fintype V] (G : SimpleGraph V) :
        randic_index G ≤ (Fintype.card V : ℝ) / 2 := by
      classical
      have hdef : randic_index G = ∑ e ∈ G.edgeFinset,
          Sym2.lift ⟨fun u v => 1/Real.sqrt ((G.degree u : ℝ) * (G.degree v : ℝ)),
            by intro a b; simp only [mul_comm]⟩ e := rfl
      rw [hdef]
      have step1 : ∑ e ∈ G.edgeFinset,
            Sym2.lift ⟨fun u v => 1/Real.sqrt ((G.degree u : ℝ) * (G.degree v : ℝ)),
              by intro a b; simp only [mul_comm]⟩ e
          ≤ ∑ e ∈ G.edgeFinset,
            Sym2.lift ⟨fun u v => (1/2) * (1/(G.degree u : ℝ) + 1/(G.degree v : ℝ)),
              by intro a b; simp only [add_comm]⟩ e := by
        refine Finset.sum_le_sum ?_
        intro e he
        induction e using Sym2.ind with
        | h u v =>
          rw [Sym2.lift_mk, Sym2.lift_mk]
          have hadde : G.Adj u v := by
            rw [← SimpleGraph.mem_edgeSet]
            exact (SimpleGraph.mem_edgeFinset).1 he
          have hu : 1 ≤ G.degree u := (SimpleGraph.degree_pos_iff_exists_adj G u).mpr ⟨v, hadde⟩
          have hv : 1 ≤ G.degree v := (SimpleGraph.degree_pos_iff_exists_adj G v).mpr ⟨u, hadde.symm⟩
          exact op1012_randic_index_le_half_card_amgm_term (G.degree u) (G.degree v) hu hv
  7. Twice the edge sum bound equals the sum of reciprocal degrees over all darts: $2 \sum_{e \in E} \frac{1}{2}(\frac{1}{\deg u} + \frac{1}{\deg v}) = \sum_{d \in \text{Dart}(G)} \frac{1}{\deg d.fst}$.

    By the edge-to-dart summation lemma, twice the edge sum of the symmetric summand $\frac{1}{2}(1/\deg u + 1/\deg v)$ equals the dart sum $\sum_d \frac{1}{2}(1/\deg d.fst + 1/\deg d.snd)$. By dart reversal invariance, $\sum_d 1/\deg d.snd = \sum_d 1/\deg d.fst$, so the dart sum simplifies directly to $\sum_d 1/\deg d.fst$.

    lines 118–127

    uses add_comm, op1012_randic_index_le_half_card_two_mul_edge_sum, Finset.sum_add_distrib, Finset.mul_sum, op1012_randic_index_le_half_card_sum_dart_snd

      have step2 := op1012_randic_index_le_half_card_two_mul_edge_sum G
        (fun u v => (1/2) * (1/(G.degree u : ℝ) + 1/(G.degree v : ℝ)))
        (by intro a b; simp only [add_comm])
      have step3 : ∑ d : G.Dart, (1/2) * (1/(G.degree d.fst : ℝ) + 1/(G.degree d.snd : ℝ))
          = ∑ d : G.Dart, 1/(G.degree d.fst : ℝ) := by
        have hsplit : ∀ d : G.Dart, (1/2) * (1/(G.degree d.fst : ℝ) + 1/(G.degree d.snd : ℝ))
            = (1/2) * (1/(G.degree d.fst : ℝ)) + (1/2) * (1/(G.degree d.snd : ℝ)) := fun d => by ring
        simp only [hsplit, Finset.sum_add_distrib, ← Finset.mul_sum]
        rw [op1012_randic_index_le_half_card_sum_dart_snd G (fun v => 1/(G.degree v : ℝ))]
        ring
  8. The dart sum $\sum_{d \in \text{Dart}(G)} \frac{1}{\deg d.fst}$ is at most $|V|$, which implies $\text{randic\_index}(G) \le |V| / 2$.

    Rewriting the dart sum as a vertex sum via the source-degree formula gives $\sum_{v \in V} \deg(v) \cdot (1/\deg v)$. For each vertex $v$, if $\deg v = 0$ the product is 0, and if $\deg v > 0$ it is $\deg(v) / \deg(v) = 1$, so in both cases each vertex contributes at most 1, making the sum at most $|V|$. Linear arithmetic combining the AM-GM bound, the edge-dart equality, and this vertex bound completes the proof that $\text{randic\_index}(G) \le |V| / 2$.

    lines 128–144

    uses op1012_randic_index_le_half_card_sum_dart_fst, mul_one_div, div_self, Finset.sum_le_sum

      have step4 : ∑ d : G.Dart, 1/(G.degree d.fst : ℝ) ≤ (Fintype.card V : ℝ) := by
        rw [op1012_randic_index_le_half_card_sum_dart_fst G (fun v => 1/(G.degree v : ℝ))]
        have hterm : ∀ v, (G.degree v : ℝ) * (1/(G.degree v : ℝ)) ≤ 1 := by
          intro v
          by_cases hv : G.degree v = 0
          · simp [hv]
          · have hv' : (G.degree v : ℝ) ≠ 0 := by exact_mod_cast hv
            rw [mul_one_div, div_self hv']
        calc ∑ v, (G.degree v : ℝ) * (1/(G.degree v : ℝ)) ≤ ∑ _v : V, (1:ℝ) :=
              Finset.sum_le_sum (fun v _ => hterm v)
          _ = (Fintype.card V : ℝ) := by simp
      have hB : ∑ e ∈ G.edgeFinset,
            Sym2.lift ⟨fun u v => (1/2) * (1/(G.degree u : ℝ) + 1/(G.degree v : ℝ)),
              by intro a b; simp only [add_comm]⟩ e
          = (1/2) * ∑ d : G.Dart, (1/2) * (1/(G.degree d.fst : ℝ) + 1/(G.degree d.snd : ℝ)) := by
        linarith [step2]
      linarith [step1, hB, step3, step4]
add_comm
In an additive commutative magma, addition is commutative: $a + b = b + a$.
div_self
A nonzero element divided by itself equals 1: $a / a = 1$ when $a \ne 0$.
div_pow
In a division commutative monoid, powers distribute over division: $(a / b)^n = a^n / b^n$.
Equiv.sum_comp
Summing a function precomposed with an equivalence of a finite type equals the sum of the original function.
Finset.card_univ
The cardinality of the universal finset `univ` of a finite type is the cardinality of that type.
Finset.mul_sum
Multiplication distributes over finite sums: $a \cdot \sum_i f(i) = \sum_i a \cdot f(i)$.
Finset.sum_add_distrib
The sum of a sum of functions equals the sum of the sums: $\sum_x (f(x) + g(x)) = \sum_x f(x) + \sum_x g(x)$.
Finset.sum_comm
Fubini's theorem for finite sums: exchanging the order of summation preserves the sum.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on all elements.
Finset.sum_const
Summing a constant $b$ over a finite set $s$ yields $|s| \cdot b$.
Finset.sum_filter
Summing over a filtered set equals summing an `if-then-else` indicator over the original set.
Finset.sum_ite_eq
Summing an indicator $\text{if } a = x \text{ then } b(x) \text{ else } 0$ over a set $s$ equals $b(a)$ if $a \in s$ and $0$ otherwise.
Finset.sum_le_sum
If $f(i) \le g(i)$ for all elements $i$ in a finite set, then $\sum_i f(i) \le \sum_i g(i)$.
Finset.sum_pair
For distinct elements $a \ne b$, the sum of a function over the two-element set $\{a, b\}$ is $f(a) + f(b)$.
Fintype.sum_equiv
A sum over a finite type can be reindexed along an equivalence (bijection) of types.
Fintype.sum_sigma
A sum over a sigma type (dependent sum) $\Sigma_{x} Y(x)$ can be rewritten as an iterated sum $\sum_x \sum_y f(x, y)$.
mul_comm
In a commutative magma, multiplication is commutative: $a \cdot b = b \cdot a$.
mul_one_div
Multiplication by a reciprocal equals division: $x \cdot (1 / y) = x / y$.
nsmul_eq_mul
Natural scalar multiplication $n \cdot a$ in a semiring equals multiplication by the coerced natural number $n \cdot a$.
one_div_mul_one_div
For elements of a division commutative monoid, $(1 / a) \cdot (1 / b) = 1 / (a \cdot b)$.
one_pow
In a monoid, $1^n = 1$.
op1012_randic_index_le_half_card_amgm_term
For positive integers $a, b \ge 1$, the reciprocal square root is bounded by the arithmetic mean: $1 / \sqrt{ab} \le \frac{1}{2}(1/a + 1/b)$.
op1012_randic_index_le_half_card_sum_dart_fst
Summing a vertex function over the first endpoint of all darts equals the degree-weighted vertex sum: $\sum_d a(d.fst) = \sum_v \deg(v) a(v)$.
op1012_randic_index_le_half_card_sum_dart_snd
Summing a vertex function over the second endpoint of all darts equals summing it over the first endpoint.
op1012_randic_index_le_half_card_two_mul_edge_sum
Twice the sum of a symmetric function over edges equals the sum of the function over all directed edges (darts).
Real.sq_sqrt
For any nonnegative real $x \ge 0$, $(\sqrt{x})^2 = x$.
Real.sqrt_mul
For any nonnegative real $x \ge 0$ and any real $y$, $\sqrt{x \cdot y} = \sqrt{x} \cdot \sqrt{y}$.
SimpleGraph.card_neighborSet_eq_degree
The number of neighbors of a vertex $v$ in a finite graph equals the degree of $v$.
SimpleGraph.Dart.edge_mem
The undirected edge corresponding to any dart belongs to the edge set of the graph.
SimpleGraph.Dart.edge_fiber
The set of darts whose underlying undirected edge is $d.\text{edge}$ consists of exactly two darts: $\{d, d.\text{symm}\}$.
SimpleGraph.Dart.symm
The reversal map sending a directed edge (dart) $(u, v)$ to the reverse directed edge $(v, u)$.
SimpleGraph.Dart.symm_ne
A dart in a simple graph is never equal to its reverse: $d.\text{symm} \ne d$.
SimpleGraph.Dart.symm_symm
Reversing a dart twice returns the original dart: $(d.\text{symm}).\text{symm} = d$.
SimpleGraph.degree_pos_iff_exists_adj
A vertex in a finite graph has positive degree ($1 \le \deg v$) if and only if it has an adjacent vertex.
SimpleGraph.mem_edgeFinset
Membership of an edge in the finite set of edges `edgeFinset` is equivalent to membership in the edge set `edgeSet`.
SimpleGraph.mem_edgeSet
An unordered pair $s(v, w)$ belongs to the edge set of a simple graph if and only if $v$ and $w$ are adjacent.
sq_nonneg
For any element in an ordered semiring, its square is nonnegative: $0 \le a^2$.
Sym2.ind
Induction principle for unordered pairs: a property holds for all $e \in \text{Sym2}(V)$ if it holds for all pairs $s(x, y)$.
Sym2.lift_mk
The lift of a symmetric function to unordered pairs evaluates on $s(a, b)$ as $f(a, b)$.

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

open Finsetprivate lemma op1012_randic_index_le_half_card_amgm_term (a b : ℕ) (ha : 1 ≤ a) (hb : 1 ≤ b) :    1 / Real.sqrt ((a:ℝ) * (b:ℝ)) ≤ (1/2) * (1/(a:ℝ) + 1/(b:ℝ)) := by  have ha' : (0:ℝ) < (a:ℝ) := by exact_mod_cast ha  have hb' : (0:ℝ) < (b:ℝ) := by exact_mod_cast hb  have key : (1/Real.sqrt (a:ℝ)) * (1/Real.sqrt (b:ℝ)) ≤      (1/2) * ((1/Real.sqrt (a:ℝ))^2 + (1/Real.sqrt (b:ℝ))^2) := by    nlinarith [sq_nonneg ((1:ℝ)/Real.sqrt (a:ℝ) - (1:ℝ)/Real.sqrt (b:ℝ))]  have ha2 : (1/Real.sqrt (a:ℝ))^2 = 1/(a:ℝ) := by    rw [div_pow, one_pow, Real.sq_sqrt ha'.le]  have hb2 : (1/Real.sqrt (b:ℝ))^2 = 1/(b:ℝ) := by    rw [div_pow, one_pow, Real.sq_sqrt hb'.le]  have hmul : (1:ℝ)/Real.sqrt ((a:ℝ)*(b:ℝ)) = (1/Real.sqrt (a:ℝ)) * (1/Real.sqrt (b:ℝ)) := by    rw [Real.sqrt_mul ha'.le, one_div_mul_one_div]  rw [hmul, ← ha2, ← hb2]  exact keyattribute [local instance] Classical.propDecidable inprivate lemma op1012_randic_index_le_half_card_two_mul_edge_sum {V : Type*} [Fintype V]    (G : SimpleGraph V) (f : V → V → ℝ) (hf : ∀ a b, f a b = f b a) :    2 * ∑ e ∈ G.edgeFinset, Sym2.lift ⟨f, hf⟩ e = ∑ d : G.Dart, f d.fst d.snd := by  classical  have hinner : ∀ e ∈ G.edgeFinset,      ∑ d ∈ (univ : Finset G.Dart).filter (fun d => d.edge = e), f d.fst d.snd        = 2 * Sym2.lift ⟨f, hf⟩ e := by    intro e    induction e using Sym2.ind with    | h u v =>      intro he      have hadde : G.Adj u v := by        rw [← SimpleGraph.mem_edgeSet]        exact (SimpleGraph.mem_edgeFinset).1 he      let d0 : G.Dart := ⟨(u, v), hadde⟩      have hfilter : (univ : Finset G.Dart).filter (fun d => d.edge = s(u, v)) = {d0, d0.symm} :=        SimpleGraph.Dart.edge_fiber d0      rw [hfilter, Finset.sum_pair (SimpleGraph.Dart.symm_ne d0).symm]      rw [Sym2.lift_mk]      show f u v + f v u = 2 * f u v      rw [hf v u]      ring  calc 2 * ∑ e ∈ G.edgeFinset, Sym2.lift ⟨f, hf⟩ e      = ∑ e ∈ G.edgeFinset, 2 * Sym2.lift ⟨f, hf⟩ e := by rw [Finset.mul_sum]    _ = ∑ e ∈ G.edgeFinset, ∑ d ∈ (univ : Finset G.Dart).filter (fun d => d.edge = e),          f d.fst d.snd := by        refine Finset.sum_congr rfl ?_        intro e he        rw [hinner e he]    _ = ∑ d : G.Dart, f d.fst d.snd := by        rw [Finset.sum_congr rfl (fun e he => Finset.sum_filter _ _), Finset.sum_comm]        refine Finset.sum_congr rfl ?_        intro d _        rw [Finset.sum_ite_eq]        simp [SimpleGraph.Dart.edge_mem]attribute [local instance] Classical.propDecidable inprivate lemma op1012_randic_index_le_half_card_sum_dart_fst {V : Type*} [Fintype V]    (G : SimpleGraph V) (a : V → ℝ) :    ∑ d : G.Dart, a d.fst = ∑ v, (G.degree v : ℝ) * a v := by  classical  let ee : G.Dart ≃ Σ v : V, G.neighborSet v :=    { toFun := fun d => ⟨d.fst, ⟨d.snd, d.adj⟩⟩      invFun := fun s => ⟨(s.1, s.2.1), s.2.2⟩      left_inv := by intro d; rfl      right_inv := by intro s; rfl }  rw [Fintype.sum_equiv ee (fun d : G.Dart => a d.fst) (fun s => a s.1) (by intro d; rfl)]  rw [Fintype.sum_sigma]  refine Finset.sum_congr rfl ?_  intro v _  have hc : (∑ y : G.neighborSet v, a ((⟨v, y⟩ : Σ w : V, G.neighborSet w).fst))      = ∑ _y : G.neighborSet v, a v :=    Finset.sum_congr rfl (fun y _ => rfl)  rw [hc]  rw [show (∑ _y : G.neighborSet v, a v) = (Fintype.card (G.neighborSet v) : ℝ) * a v from by    simp [Finset.sum_const, Finset.card_univ, nsmul_eq_mul]]  rw [SimpleGraph.card_neighborSet_eq_degree]attribute [local instance] Classical.propDecidable inprivate lemma op1012_randic_index_le_half_card_sum_dart_snd {V : Type*} [Fintype V]    (G : SimpleGraph V) (a : V → ℝ) :    ∑ d : G.Dart, a d.snd = ∑ d : G.Dart, a d.fst := by  classical  let σ : G.Dart ≃ G.Dart :=    { toFun := SimpleGraph.Dart.symm      invFun := SimpleGraph.Dart.symm      left_inv := fun d => SimpleGraph.Dart.symm_symm d      right_inv := fun d => SimpleGraph.Dart.symm_symm d }  have h := Equiv.sum_comp σ (fun d : G.Dart => a d.fst)  simpa [σ] using hattribute [local instance] Classical.propDecidable in/-- Upper bound on the Randić index: for any finite simple graph G, R(G) ≤ |V| / 2. -/theorem op1012_randic_index_le_half_card    {V : Type*} [Fintype V] (G : SimpleGraph V) :    randic_index G ≤ (Fintype.card V : ℝ) / 2 := by  classical  have hdef : randic_index G = ∑ e ∈ G.edgeFinset,      Sym2.lift ⟨fun u v => 1/Real.sqrt ((G.degree u : ℝ) * (G.degree v : ℝ)),        by intro a b; simp only [mul_comm]⟩ e := rfl  rw [hdef]  have step1 : ∑ e ∈ G.edgeFinset,        Sym2.lift ⟨fun u v => 1/Real.sqrt ((G.degree u : ℝ) * (G.degree v : ℝ)),          by intro a b; simp only [mul_comm]⟩ e      ≤ ∑ e ∈ G.edgeFinset,        Sym2.lift ⟨fun u v => (1/2) * (1/(G.degree u : ℝ) + 1/(G.degree v : ℝ)),          by intro a b; simp only [add_comm]⟩ e := by    refine Finset.sum_le_sum ?_    intro e he    induction e using Sym2.ind with    | h u v =>      rw [Sym2.lift_mk, Sym2.lift_mk]      have hadde : G.Adj u v := by        rw [← SimpleGraph.mem_edgeSet]        exact (SimpleGraph.mem_edgeFinset).1 he      have hu : 1 ≤ G.degree u := (SimpleGraph.degree_pos_iff_exists_adj G u).mpr ⟨v, hadde⟩      have hv : 1 ≤ G.degree v := (SimpleGraph.degree_pos_iff_exists_adj G v).mpr ⟨u, hadde.symm⟩      exact op1012_randic_index_le_half_card_amgm_term (G.degree u) (G.degree v) hu hv  have step2 := op1012_randic_index_le_half_card_two_mul_edge_sum G    (fun u v => (1/2) * (1/(G.degree u : ℝ) + 1/(G.degree v : ℝ)))    (by intro a b; simp only [add_comm])  have step3 : ∑ d : G.Dart, (1/2) * (1/(G.degree d.fst : ℝ) + 1/(G.degree d.snd : ℝ))      = ∑ d : G.Dart, 1/(G.degree d.fst : ℝ) := by    have hsplit : ∀ d : G.Dart, (1/2) * (1/(G.degree d.fst : ℝ) + 1/(G.degree d.snd : ℝ))        = (1/2) * (1/(G.degree d.fst : ℝ)) + (1/2) * (1/(G.degree d.snd : ℝ)) := fun d => by ring    simp only [hsplit, Finset.sum_add_distrib, ← Finset.mul_sum]    rw [op1012_randic_index_le_half_card_sum_dart_snd G (fun v => 1/(G.degree v : ℝ))]    ring  have step4 : ∑ d : G.Dart, 1/(G.degree d.fst : ℝ) ≤ (Fintype.card V : ℝ) := by    rw [op1012_randic_index_le_half_card_sum_dart_fst G (fun v => 1/(G.degree v : ℝ))]    have hterm : ∀ v, (G.degree v : ℝ) * (1/(G.degree v : ℝ)) ≤ 1 := by      intro v      by_cases hv : G.degree v = 0      · simp [hv]      · have hv' : (G.degree v : ℝ) ≠ 0 := by exact_mod_cast hv        rw [mul_one_div, div_self hv']    calc ∑ v, (G.degree v : ℝ) * (1/(G.degree v : ℝ)) ≤ ∑ _v : V, (1:ℝ) :=          Finset.sum_le_sum (fun v _ => hterm v)      _ = (Fintype.card V : ℝ) := by simp  have hB : ∑ e ∈ G.edgeFinset,        Sym2.lift ⟨fun u v => (1/2) * (1/(G.degree u : ℝ) + 1/(G.degree v : ℝ)),          by intro a b; simp only [add_comm]⟩ e      = (1/2) * ∑ d : G.Dart, (1/2) * (1/(G.degree d.fst : ℝ) + 1/(G.degree d.snd : ℝ)) := by    linarith [step2]  linarith [step1, hB, step3, step4]
See it in the graphDiscuss this resultChallenge it