op1012_complete_bipartite_randic_index
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).
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.
uses
Classical.propDecidableclassical letI : DecidableRel (completeBipartiteGraph (Fin a) (Fin b)).Adj := fun x y => Classical.propDecidable _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.
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_finhave 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]
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.
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_finhave 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]
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.
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_univrw [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
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).
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.
- The Randić index is defined as a sum over unordered pairs (elements of `Sym2`), so the proof explicitly sets up a bijection with `Fin a × Fin b` via `Finset.sum_bij`.
- The final simplification showing that (a * b) * (1 / √(a * b)) = √(a * b) relies on `nlinarith` combined with the identity (√(a * b))² = 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
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 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]