op1012_randic_index_le_half_card
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.
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.
uses
sq_nonneg,div_pow,one_pow,Real.sq_sqrt,Real.sqrt_mul,one_div_mul_one_divopen 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
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$.
uses
Sym2.ind,SimpleGraph.mem_edgeSet,SimpleGraph.mem_edgeFinset,SimpleGraph.Dart.edge_fiber,Finset.sum_pair,SimpleGraph.Dart.symm_ne,Sym2.lift_mkattribute [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
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$.
uses
Finset.mul_sum,Finset.sum_congr,Finset.sum_filter,Finset.sum_comm,Finset.sum_ite_eq,SimpleGraph.Dart.edge_memcalc 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]
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)$.
uses
Fintype.sum_equiv,Fintype.sum_sigma,Finset.sum_congr,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,SimpleGraph.card_neighborSet_eq_degreeattribute [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]
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)$.
uses
SimpleGraph.Dart.symm,SimpleGraph.Dart.symm_symm,Equiv.sum_compattribute [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
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.
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_termattribute [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
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$.
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_sndhave 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
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$.
uses
op1012_randic_index_le_half_card_sum_dart_fst,mul_one_div,div_self,Finset.sum_le_sumhave 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)$.
- In Lean, real division by zero is defined to be zero ($1/0 = 0$), so an isolated vertex $v$ with $\deg v = 0$ satisfies $\deg(v) \cdot (1/\deg v) = 0 \le 1$, handled by an explicit case split with no counterpart needed on paper where isolated vertices simply have no incident edges.
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.
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]