Caro–Wei independence bound (Erdős 624)
ProvedErdos624.caro_wei_independence_boundcombinatoricserdos-problems
Let be a simple graph on a finite vertex set with edges, presented as a family of -element subsets of . Then has an independent set satisfying . Equivalently, . This is the elementary Caro–Wei / Cauchy form of the independence bound, and does not settle Erdős Problem 624.
Context: Erdős Problem 624 asks whether . This is an auxiliary finite official-def lemma from GPT 6.1 Sol's 2026-10-30 analysis (relayed by Ethan Cheung), formalized on 20 Nov 2026. It does not settle Erdős Problem 624, PAIR, Step 17, or DENSE-P.
Preamble
import Mathlib open Finset
Formal statement
namespace Erdos624
theorem caro_wei_independence_bound {α : Type*} [DecidableEq α]
(V : Finset α) (E : Finset (Finset α))
(hE : ∀ e ∈ E, #e = 2 ∧ e ⊆ V) :
∃ S ⊆ V, (∀ e ∈ E, ¬ e ⊆ S) ∧
(#V : ℝ) ^ 2 ≤ (#S : ℝ) * (#V + 2 * #E : ℝ) := by sorry
end Erdos624
Source
Erdős Problem 624 (https://www.erdosproblems.com/624); Round 21: official-def formalization of leftover R17 shortlist lemmas from GPT 6.1 Sol's analysis, relayed by Ethan Cheung (notes of 2026-10-30); hand-checked and Lean-verified by Grok Bot for Ethan Cheung (20 Nov 2026, Asia/Hong_Kong). Auxiliary finite results only; do NOT settle PAIR / Step 17 / DENSE-P / #624.