simple_graph_binding_number_le_iff
For a graph on a nonempty finite vertex set, bind(G) ≤ c iff some nonempty S with N(S) ≠ V has |N(S)| ≤ c|S| (the infimum is a minimum over a finite nonempty family: every singleton is admissible since v ∉ N(v)).
Statement
theorem simple_graph_binding_number_le_iff {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V] (G : SimpleGraph V) [DecidableRel G.Adj] (c : ℝ) : simple_graph_binding_number G ≤ c ↔ ∃ S : Finset V, S.Nonempty ∧ S.biUnion (fun v => G.neighborFinset v) ≠ Finset.univ ∧ ((S.biUnion (fun v => G.neighborFinset v)).card : ℝ) ≤ c * S.card
- Source
- sanity lemma for simple_graph_binding_number; serves OP-422
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_binding_numberbind(G) = min{|N_G(S)|/|S| : ∅ ≠ S ⊆ V(G), N_G(S) ≠ V(G)}, where N_G(S) is the union of the neighbourhoods of the vertices of S.
- Used by 2
- simple_graph_binding_number_completeThe complete graph K_n (n ≥ 2) has binding number n − 1: a singleton {v} has N = V∖{v}, and any S with two vertices has N(S) = V.
- simple_graph_binding_number_complete_four_partiteThe complete 4-partite graph with four parts of size m ≥ 1 is K_5-free and has binding number exactly 3, so the bound 3 conjectured for…
The proof, explained
The binding number of a graph G is defined as the infimum of |N(S)|/|S| over all nonempty vertex subsets S whose neighborhood is not the full vertex set V. Since V is nonempty and simple graphs have no self-loops, singleton subsets are always admissible, so the collection of candidate subsets is finite and nonempty. Because the infimum of a function over a finite nonempty set is achieved as a minimum, the infimum is at most c if and only if some candidate set achieves ratio at most c. Multiplying through by the positive cardinality |S| shows this is equivalent to |N(S)| ≤ c|S|.
The index set ι of candidate subsets S ⊆ V (nonempty sets whose neighborhood is not all of V) is nonempty.
We define ι as the subtype of subsets S with S nonempty and N(S) ≠ V. Since V is nonempty, pick an arbitrary vertex v (called `default`). The singleton {v} is nonempty by `Finset.singleton_nonempty`. Since simple graphs have no self-loops, v ∉ N(v) = N({v}). If N({v}) were all of V, then v would belong to N({v}) by `Finset.mem_univ`, which is a contradiction. Hence N({v}) ≠ V, showing that {v} is an element of ι.
uses
Finset.singleton_nonempty,Finset.mem_univlet ι := {S : Finset V // S.Nonempty ∧ S.biUnion (fun v => G.neighborFinset v) ≠ Finset.univ} have : Nonempty ι := by inhabit V refine ⟨⟨{default}, Finset.singleton_nonempty _, ?_⟩⟩ intro h have hnv : (default : V) ∉ ({default} : Finset V).biUnion (fun u => G.neighborFinset u) := by simp rw [h] at hnv exact hnv (Finset.mem_univ _)
The condition bind(G) ≤ c is equivalent to ⨅ S : ι, f(S) ≤ c, where f(S) = |N(S)| / |S|.
We define the ratio function f(S) = |N(S)| / |S| on ι. Unfolding the definition of `simple_graph_binding_number`, the condition bind(G) ≤ c is by definition ⨅ S : ι, f(S) ≤ c. We split the equivalence into two directions.
let f : ι → ℝ := fun S => ((S.1.biUnion (fun v => G.neighborFinset v)).card : ℝ) / S.1.card change ⨅ S : ι, f S ≤ c ↔ _ constructor
If bind(G) ≤ c, then there exists a candidate set S with |N(S)| ≤ c|S|.
Assume ⨅ S : ι, f(S) ≤ c. Since V is finite, the index type ι is finite; because it is also nonempty, the infimum of f over ι is attained at some minimizer S by `exists_eq_ciInf_of_finite`. Thus f(S) ≤ c. Since S is nonempty, |S| > 0 (via `Nat.cast_pos.mpr`). Multiplying f(S) = |N(S)| / |S| ≤ c by |S| using `div_le_iff₀` gives |N(S)| ≤ c|S|, providing the required witness S.
uses
exists_eq_ciInf_of_finite,Nat.cast_pos.mpr,div_le_iff₀· intro h obtain ⟨S, hS⟩ : ∃ S : ι, f S = ⨅ S : ι, f S := exists_eq_ciInf_of_finite rw [← hS] at h refine ⟨S.1, S.2.1, S.2.2, ?_⟩ have hcard : 0 < (S.1.card : ℝ) := Nat.cast_pos.mpr S.2.1.card_pos exact (div_le_iff₀ hcard).mp h
If some candidate set S has |N(S)| ≤ c|S|, then bind(G) ≤ c.
Given a nonempty set S with N(S) ≠ V and |N(S)| ≤ c|S|, we package S into an element s of ι. Since |S| > 0 by `Nat.cast_pos.mpr`, dividing by |S| via `div_le_iff₀` yields f(s) ≤ c. Because ι is finite, the range of f is bounded below by `Finite.bddBelow_range`, so the infimum satisfies ⨅ T : ι, f(T) ≤ f(s) ≤ c by `ciInf_le_of_le`.
uses
Nat.cast_pos.mpr,div_le_iff₀,Finite.bddBelow_range,ciInf_le_of_le· rintro ⟨S, hne, huniv, hle⟩ let s : ι := ⟨S, ⟨hne, huniv⟩⟩ have hcard : 0 < (S.card : ℝ) := Nat.cast_pos.mpr hne.card_pos have hfs : f s ≤ c := (div_le_iff₀ hcard).mpr hle exact ciInf_le_of_le (Finite.bddBelow_range f) s hfs
Finset.singleton_nonempty- For any element a, the singleton set {a} is nonempty.
Finset.mem_univ- In a finite type, every element belongs to the universal finset `univ`.
exists_eq_ciInf_of_finite- The infimum of a function from a finite, nonempty type into a conditionally complete linear order is attained as a minimum at some element.
Nat.cast_pos.mpr- A natural number is strictly positive if and only if its cast to a linearly ordered field is strictly positive.
div_le_iff₀- For a positive element c > 0, b / c ≤ a if and only if b ≤ a * c.
ciInf_le_of_le- If the range of a function f is bounded below and f(s) ≤ a for some index s, then ⨅ f ≤ a.
Finite.bddBelow_range- The range of any function from a finite type into a preorder is bounded below.
- On line 11, `simp` automatically uses the irreflexivity of simple graphs (no self-loops) to deduce that a vertex is not in its own open neighborhood.
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.
theorem simple_graph_binding_number_le_iff {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V] (G : SimpleGraph V) [DecidableRel G.Adj] (c : ℝ) : simple_graph_binding_number G ≤ c ↔ ∃ S : Finset V, S.Nonempty ∧ S.biUnion (fun v => G.neighborFinset v) ≠ Finset.univ ∧ ((S.biUnion (fun v => G.neighborFinset v)).card : ℝ) ≤ c * S.card := by let ι := {S : Finset V // S.Nonempty ∧ S.biUnion (fun v => G.neighborFinset v) ≠ Finset.univ} have : Nonempty ι := by inhabit V refine ⟨⟨{default}, Finset.singleton_nonempty _, ?_⟩⟩ intro h have hnv : (default : V) ∉ ({default} : Finset V).biUnion (fun u => G.neighborFinset u) := by simp rw [h] at hnv exact hnv (Finset.mem_univ _) let f : ι → ℝ := fun S => ((S.1.biUnion (fun v => G.neighborFinset v)).card : ℝ) / S.1.card change ⨅ S : ι, f S ≤ c ↔ _ constructor · intro h obtain ⟨S, hS⟩ : ∃ S : ι, f S = ⨅ S : ι, f S := exists_eq_ciInf_of_finite rw [← hS] at h refine ⟨S.1, S.2.1, S.2.2, ?_⟩ have hcard : 0 < (S.1.card : ℝ) := Nat.cast_pos.mpr S.2.1.card_pos exact (div_le_iff₀ hcard).mp h · rintro ⟨S, hne, huniv, hle⟩ let s : ι := ⟨S, ⟨hne, huniv⟩⟩ have hcard : 0 < (S.card : ℝ) := Nat.cast_pos.mpr hne.card_pos have hfs : f s ≤ c := (div_le_iff₀ hcard).mpr hle exact ciInf_le_of_le (Finite.bddBelow_range f) s hfs