AFTD Auto-Formalizing Theoretical Domains

op1012_complete_bipartite_randic_index

theoremverifiedformalization

For any positive integers a and b, the Randić index of the complete bipartite graph completeBipartiteGraph (Fin a) (Fin b) equals Real.sqrt ((a : ℝ) * (b : ℝ)).

Statement

attribute [local instance] Classical.propDecidable in
theorem op1012_complete_bipartite_randic_index
    (a b : ℕ) (ha : 1 ≤ a) (hb : 1 ≤ b) :
    randic_index (completeBipartiteGraph (Fin a) (Fin b)) = Real.sqrt ((a : ℝ) * (b : ℝ))
Formalizes
arXiv:2611.03879 Conjecture 3 text
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 natural numbers $a$ and $b$ such that $1 \le a$ and $1 \le b$, the Randić index of the complete bipartite graph with parts $\text{Fin } a$ and $\text{Fin } b$ equals $\sqrt{a \cdot b}$ (where $a$ and $b$ are cast to real numbers).

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 the sum over all edges {u, v} of 1 / √(d(u)d(v)). For the complete bipartite graph K_{a,b}, every vertex in the first part has degree b and every vertex in the second part has degree a. Consequently, each of the a * b edges contributes 1 / √(ab) to the sum. The total sum is therefore (ab) / √(ab) = √(ab).

  1. Enable classical logic and declare decidability for the graph adjacency relation.

    We activate classical reasoning and provide an instance of decidability for adjacency in the complete bipartite graph, enabling degrees and neighbor sets to be treated as finite sets.

    lines 6–7

    uses Classical.propDecidable

      classical
      letI : DecidableRel (completeBipartiteGraph (Fin a) (Fin b)).Adj := fun x y => Classical.propDecidable _
  2. Every vertex in the first part Fin a has degree b.

    The degree of a vertex is the size of its neighbor finset. For any vertex inl(i), its neighbors in the complete bipartite graph are precisely the image of Fin b under Sum.inr. Because Sum.inr is injective, the cardinality of this image equals the size of Fin b, which is b.

    lines 8–25

    uses SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.mem_neighborFinset, Finset.mem_image, Finset.mem_univ, true_and, completeBipartiteGraph_adj, Finset.card_image_of_injective, Sum.inr_injective, Finset.card_univ, Fintype.card_fin

      have hdeg_inl : ∀ i : Fin a, (completeBipartiteGraph (Fin a) (Fin b)).degree (Sum.inl i) = b := by
        intro i
        rw [← SimpleGraph.card_neighborFinset_eq_degree]
        have h : (completeBipartiteGraph (Fin a) (Fin b)).neighborFinset (Sum.inl i)
            = (Finset.univ : Finset (Fin b)).image Sum.inr := by
          ext w
          simp only [SimpleGraph.mem_neighborFinset, Finset.mem_image, Finset.mem_univ, true_and]
          constructor
          · intro hw
            rw [completeBipartiteGraph_adj] at hw
            cases w with
            | inl x => simp at hw
            | inr y => exact ⟨y, rfl⟩
          · rintro ⟨j, rfl⟩
            rw [completeBipartiteGraph_adj]
            simp
        rw [h, Finset.card_image_of_injective _ Sum.inr_injective, Finset.card_univ,
          Fintype.card_fin]
  3. Every vertex in the second part Fin b has degree a.

    Symmetrically, the neighbors of inr(j) are the vertices in the image of Fin a under Sum.inl. By injectivity of Sum.inl, this neighborhood has cardinality equal to |Fin a| = a.

    lines 26–43

    uses SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.mem_neighborFinset, Finset.mem_image, Finset.mem_univ, true_and, completeBipartiteGraph_adj, Finset.card_image_of_injective, Sum.inl_injective, Finset.card_univ, Fintype.card_fin

      have hdeg_inr : ∀ j : Fin b, (completeBipartiteGraph (Fin a) (Fin b)).degree (Sum.inr j) = a := by
        intro j
        rw [← SimpleGraph.card_neighborFinset_eq_degree]
        have h : (completeBipartiteGraph (Fin a) (Fin b)).neighborFinset (Sum.inr j)
            = (Finset.univ : Finset (Fin a)).image Sum.inl := by
          ext w
          simp only [SimpleGraph.mem_neighborFinset, Finset.mem_image, Finset.mem_univ, true_and]
          constructor
          · intro hw
            rw [completeBipartiteGraph_adj] at hw
            cases w with
            | inl x => exact ⟨x, rfl⟩
            | inr y => simp at hw
          · rintro ⟨i, rfl⟩
            rw [completeBipartiteGraph_adj]
            simp
        rw [h, Finset.card_image_of_injective _ Sum.inl_injective, Finset.card_univ,
          Fintype.card_fin]
  4. The Randić index sum over the edge set is equivalent to a sum over Fin a × Fin b.

    By definition, the Randić index sums 1 / √(d(u) * d(v)) over the edge finset. Using Finset.sum_bij, we re-index this sum over the Cartesian product Fin a × Fin b via (i, j) ↦ s(inl(i), inr(j)). This map is well-defined onto the edges of K_{a,b}, injective (because left and right components cannot cross), and surjective.

    lines 44–61

    uses randic_index, Eq.trans, Finset.sum_bij, Sym2.lift, mul_comm, SimpleGraph.mem_edgeFinset, SimpleGraph.edgeSet_completeBipartiteGraph, Sym2.eq, Sym2.rel_iff, Prod.ext, Sum.inl_injective, Sum.inr_injective, Sum.inl_ne_inr, Finset.mem_univ

      rw [randic_index]
      refine Eq.trans (Finset.sum_bij (s := (Finset.univ : Finset (Fin a × Fin b)))
        (f := fun p => Sym2.lift ⟨fun u v => 1 / Real.sqrt (((completeBipartiteGraph (Fin a) (Fin b)).degree u : ℝ) * ((completeBipartiteGraph (Fin a) (Fin b)).degree v : ℝ)), by intro u v; simp [mul_comm]⟩ s(Sum.inl p.1, Sum.inr p.2))
        (fun p _ => s(Sum.inl p.1, Sum.inr p.2)) ?_ ?_ ?_ ?_).symm ?_
      · intro p _
        rw [SimpleGraph.mem_edgeFinset, SimpleGraph.edgeSet_completeBipartiteGraph]
        exact ⟨p, rfl⟩
      · intro p _ q _ hpq
        rw [Sym2.eq, Sym2.rel_iff] at hpq
        rcases hpq with ⟨h1, h2⟩ | ⟨h1, h2⟩
        · exact Prod.ext (Sum.inl_injective h1) (Sum.inr_injective h2)
        · exact absurd h1 Sum.inl_ne_inr
      · intro e he
        rw [SimpleGraph.mem_edgeFinset, SimpleGraph.edgeSet_completeBipartiteGraph] at he
        obtain ⟨p, hp⟩ := he
        exact ⟨p, Finset.mem_univ _, hp⟩
      · intro p _
        rfl
  5. The sum evaluates to √(a * b).

    Unfolding the symmetric lift on edges, each term for (i, j) evaluates to 1 / √(b * a) = 1 / √(a * b) using the vertex degrees computed earlier. Since all a * b terms are identical, the sum is (a * b) * (1 / √(a * b)). Because a ≥ 1 and b ≥ 1, the product a * b is strictly positive, giving (√(a * b))² = a * b, from which nonlinear arithmetic concludes that (a * b) / √(a * b) = √(a * b).

    lines 62–75

    uses Sym2.lift_mk, mul_comm, Finset.sum_const, Finset.card_univ, Fintype.card_prod, Fintype.card_fin, nsmul_eq_mul, mul_pos, Real.sq_sqrt, le_of_lt

      · simp only [Sym2.lift_mk]
        have hterm : ∀ x : Fin a × Fin b,
            (1 : ℝ) / Real.sqrt ((↑((completeBipartiteGraph (Fin a) (Fin b)).degree (Sum.inl x.1)) : ℝ) * ↑((completeBipartiteGraph (Fin a) (Fin b)).degree (Sum.inr x.2))) = 1 / Real.sqrt ((a:ℝ)*(b:ℝ)) := by
          intro x
          rw [hdeg_inl, hdeg_inr, mul_comm]
        simp only [hterm]
        simp only [Finset.sum_const, Finset.card_univ, Fintype.card_prod, Fintype.card_fin, nsmul_eq_mul]
        have ha' : (0:ℝ) < (a:ℝ) := by exact_mod_cast ha
        have hb' : (0:ℝ) < (b:ℝ) := by exact_mod_cast hb
        have hab : (0:ℝ) < (a:ℝ) * (b:ℝ) := mul_pos ha' hb'
        have hsq := Real.sq_sqrt (le_of_lt hab)
        push_cast
        field_simp
        nlinarith [hsq]
Classical.propDecidable
Every proposition is decidable under classical logic.
SimpleGraph.card_neighborFinset_eq_degree
The degree of a vertex in a graph equals the cardinality of its neighbor finset.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
Finset.mem_image
An element b belongs to the image f(s) of a finset s if and only if b = f(a) for some a ∈ s.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
true_and
The logical conjunction True ∧ p simplifies to p.
completeBipartiteGraph_adj
Two vertices in a complete bipartite graph are adjacent if and only if one is in the left part and the other is in the right part.
Finset.card_image_of_injective
The cardinality of the image of a finite set under an injective map equals the cardinality of the original set.
Sum.inr_injective
The canonical injection Sum.inr into a disjoint sum type is injective.
Sum.inl_injective
The canonical injection Sum.inl into a disjoint sum type is injective.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of the finite type Fin n is n.
randic_index
The Randić index of a graph is the sum over all edges {u, v} of 1 / √(degree u * degree v).
Eq.trans
Equality is transitive: if a = b and b = c, then a = c.
Finset.sum_bij
Two finite sums are equal if there is a bijection between their indexing sets that preserves summands.
Sym2.lift
Lifts a symmetric binary operation on vertices to a well-defined function on unordered pairs (edges).
mul_comm
Multiplication is commutative: a * b = b * a.
SimpleGraph.mem_edgeFinset
An unordered pair belongs to the edge finset of a graph if and only if it belongs to its edge set.
SimpleGraph.edgeSet_completeBipartiteGraph
The edge set of a complete bipartite graph consists of all unordered pairs formed by one vertex from each part.
Sym2.eq
Two unordered pairs are equal if and only if their underlying pairs are related by the unordered pair equivalence relation.
Sym2.rel_iff
Two pairs (x, y) and (z, w) define the same unordered pair if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
Prod.ext
Two ordered pairs are equal if their corresponding components are equal.
Sum.inl_ne_inr
An element in the left part of a sum type is never equal to an element in the right part.
Sym2.lift_mk
Evaluating the symmetric lift of a function on an unordered pair s(a, b) yields the underlying function evaluated on (a, b).
Finset.sum_const
Summing a constant value over a finite set equals the cardinality of the set multiplied by that constant.
Fintype.card_prod
The cardinality of a Cartesian product of finite types is the product of their individual cardinalities.
nsmul_eq_mul
Scalar multiplication by a natural number n in a semiring is ordinary multiplication by n.
mul_pos
The product of two strictly positive numbers is strictly positive.
Real.sq_sqrt
The square of the square root of a non-negative real number x is x.
le_of_lt
A strict inequality a < b implies 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

attribute [local instance] Classical.propDecidable in/-- The Randić index of the complete bipartite graph K_{a,b} equals sqrt(a * b). -/theorem op1012_complete_bipartite_randic_index    (a b : ℕ) (ha : 1 ≤ a) (hb : 1 ≤ b) :    randic_index (completeBipartiteGraph (Fin a) (Fin b)) = Real.sqrt ((a : ℝ) * (b : ℝ)) := by  classical  letI : DecidableRel (completeBipartiteGraph (Fin a) (Fin b)).Adj := fun x y => Classical.propDecidable _  have hdeg_inl : ∀ i : Fin a, (completeBipartiteGraph (Fin a) (Fin b)).degree (Sum.inl i) = b := by    intro i    rw [← SimpleGraph.card_neighborFinset_eq_degree]    have h : (completeBipartiteGraph (Fin a) (Fin b)).neighborFinset (Sum.inl i)        = (Finset.univ : Finset (Fin b)).image Sum.inr := by      ext w      simp only [SimpleGraph.mem_neighborFinset, Finset.mem_image, Finset.mem_univ, true_and]      constructor      · intro hw        rw [completeBipartiteGraph_adj] at hw        cases w with        | inl x => simp at hw        | inr y => exact ⟨y, rfl⟩      · rintro ⟨j, rfl⟩        rw [completeBipartiteGraph_adj]        simp    rw [h, Finset.card_image_of_injective _ Sum.inr_injective, Finset.card_univ,      Fintype.card_fin]  have hdeg_inr : ∀ j : Fin b, (completeBipartiteGraph (Fin a) (Fin b)).degree (Sum.inr j) = a := by    intro j    rw [← SimpleGraph.card_neighborFinset_eq_degree]    have h : (completeBipartiteGraph (Fin a) (Fin b)).neighborFinset (Sum.inr j)        = (Finset.univ : Finset (Fin a)).image Sum.inl := by      ext w      simp only [SimpleGraph.mem_neighborFinset, Finset.mem_image, Finset.mem_univ, true_and]      constructor      · intro hw        rw [completeBipartiteGraph_adj] at hw        cases w with        | inl x => exact ⟨x, rfl⟩        | inr y => simp at hw      · rintro ⟨i, rfl⟩        rw [completeBipartiteGraph_adj]        simp    rw [h, Finset.card_image_of_injective _ Sum.inl_injective, Finset.card_univ,      Fintype.card_fin]  rw [randic_index]  refine Eq.trans (Finset.sum_bij (s := (Finset.univ : Finset (Fin a × Fin b)))    (f := fun p => Sym2.lift ⟨fun u v => 1 / Real.sqrt (((completeBipartiteGraph (Fin a) (Fin b)).degree u : ℝ) * ((completeBipartiteGraph (Fin a) (Fin b)).degree v : ℝ)), by intro u v; simp [mul_comm]⟩ s(Sum.inl p.1, Sum.inr p.2))    (fun p _ => s(Sum.inl p.1, Sum.inr p.2)) ?_ ?_ ?_ ?_).symm ?_  · intro p _    rw [SimpleGraph.mem_edgeFinset, SimpleGraph.edgeSet_completeBipartiteGraph]    exact ⟨p, rfl⟩  · intro p _ q _ hpq    rw [Sym2.eq, Sym2.rel_iff] at hpq    rcases hpq with ⟨h1, h2⟩ | ⟨h1, h2⟩    · exact Prod.ext (Sum.inl_injective h1) (Sum.inr_injective h2)    · exact absurd h1 Sum.inl_ne_inr  · intro e he    rw [SimpleGraph.mem_edgeFinset, SimpleGraph.edgeSet_completeBipartiteGraph] at he    obtain ⟨p, hp⟩ := he    exact ⟨p, Finset.mem_univ _, hp⟩  · intro p _    rfl  · simp only [Sym2.lift_mk]    have hterm : ∀ x : Fin a × Fin b,        (1 : ℝ) / Real.sqrt ((↑((completeBipartiteGraph (Fin a) (Fin b)).degree (Sum.inl x.1)) : ℝ) * ↑((completeBipartiteGraph (Fin a) (Fin b)).degree (Sum.inr x.2))) = 1 / Real.sqrt ((a:ℝ)*(b:ℝ)) := by      intro x      rw [hdeg_inl, hdeg_inr, mul_comm]    simp only [hterm]    simp only [Finset.sum_const, Finset.card_univ, Fintype.card_prod, Fintype.card_fin, nsmul_eq_mul]    have ha' : (0:ℝ) < (a:ℝ) := by exact_mod_cast ha    have hb' : (0:ℝ) < (b:ℝ) := by exact_mod_cast hb    have hab : (0:ℝ) < (a:ℝ) * (b:ℝ) := mul_pos ha' hb'    have hsq := Real.sq_sqrt (le_of_lt hab)    push_cast    field_simp    nlinarith [hsq]
See it in the graphDiscuss this resultChallenge it