AFTD Auto-Formalizing Theoretical Domains

simple_graph_binding_number_le_iff

theoremverified

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

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|.

  1. 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 ι.

    lines 6–13

    uses Finset.singleton_nonempty, Finset.mem_univ

      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 _)
  2. 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.

    lines 14–16

      let f : ι → ℝ := fun S => ((S.1.biUnion (fun v => G.neighborFinset v)).card : ℝ) / S.1.card
      change ⨅ S : ι, f S ≤ c ↔ _
      constructor
  3. 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.

    lines 17–22

    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
  4. 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`.

    lines 23–27

    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.

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

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
See it in the graphDiscuss this resultChallenge it