AFTD Auto-Formalizing Theoretical Domains

simple_graph_binding_number_complete

theoremverified

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

Statement

theorem simple_graph_binding_number_complete (n : ℕ) (hn : 2 ≤ n) :
    simple_graph_binding_number (⊤ : SimpleGraph (Fin n)) = (n : ℝ) - 1
Source
sanity lemma for simple_graph_binding_number; serves OP-422
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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.
  • simple_graph_binding_number_le_iffFor 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…

The proof, explained

The binding number of a simple graph is defined as the infimum of |N(S)| / |S| over all nonempty subsets S with N(S) ≠ V. The proof establishes the value n − 1 for the complete graph K_n (with n ≥ 2) by proving both inequalities. For the upper bound, testing on any singleton S = {v} gives N(S) = V ∖ {v}, achieving the ratio (n − 1) / 1 = n − 1; for the lower bound, any set S with at least two vertices would have N(S) = V, which forces every valid candidate S in the infimum to be a singleton, making n − 1 the exact minimum.

  1. It suffices to prove both simple_graph_binding_number ⊤ ≤ n - 1 and n - 1 ≤ simple_graph_binding_number ⊤.

    By antisymmetry of the partial order on ℝ, equality holds if each side is less than or equal to the other.

    line 3

    uses le_antisymm

      refine le_antisymm ?_ ?_
  2. To establish the upper bound, it suffices to exhibit a nonempty set S with N(S) ≠ V and |N(S)| ≤ (n - 1) |S|, which we choose to be the singleton {v} for v = 0.

    Since n ≥ 2, the vertex set Fin n is nonempty, so we may define a vertex v = 0. By simple_graph_binding_number_le_iff, finding any nonempty set S whose neighborhood is not the whole vertex set V such that |N(S)| ≤ (n - 1)|S| proves that the binding number is at most n - 1. We choose S = {v}, which is nonempty.

    lines 4–7

    uses simple_graph_binding_number_le_iff, Finset.singleton_nonempty

      · have : Nonempty (Fin n) := ⟨⟨0, by omega⟩⟩
        rw [simple_graph_binding_number_le_iff]
        let v : Fin n := ⟨0, by omega⟩
        refine ⟨{v}, Finset.singleton_nonempty v, ?_, ?_⟩
  3. The neighborhood N({v}) is not the entire vertex set.

    The union of neighborhoods for the singleton {v} is simply the neighborhood N(v). If N(v) were the entire vertex set Fin n, then v would be adjacent to itself, contradicting the fact that simple graphs contain no self-loops.

    lines 8–12

    uses Finset.singleton_biUnion, Finset.mem_univ

        · simp only [Finset.singleton_biUnion]
          intro h
          have : v ∉ (⊤ : SimpleGraph (Fin n)).neighborFinset v := by simp
          rw [h] at this
          exact this (Finset.mem_univ v)
  4. The ratio inequality |N({v})| ≤ (n - 1) |{v}| holds.

    Since |{v}| = 1, the right-hand side simplifies to n - 1. In the complete graph K_n, the neighbors of v are all vertices except v itself, so N(v) = V ∖ {v}, which has cardinality |V| - 1 = n - 1. The desired inequality then holds as an exact equality.

    lines 13–18

    uses Finset.singleton_biUnion, Finset.card_singleton, Nat.cast_one, mul_one, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, Fintype.card_fin, le_of_eq, Nat.cast_pred

        · simp only [Finset.singleton_biUnion, Finset.card_singleton, Nat.cast_one, mul_one]
          have hnv : (⊤ : SimpleGraph (Fin n)).neighborFinset v = Finset.univ.erase v := by
            ext x; simp
          rw [hnv, Finset.card_erase_of_mem (Finset.mem_univ v), Finset.card_univ, Fintype.card_fin]
          have : 1 ≤ n := by omega
          exact le_of_eq (Nat.cast_pred this)
  5. The collection of candidate subsets S (nonempty sets with N(S) ≠ V) is nonempty.

    Before bounding the infimum, we establish that its indexing subtype is inhabited by checking that the singleton {v} satisfies N({v}) ≠ V, which again follows because v is not a neighbor of itself.

    lines 19–27

    uses Finset.singleton_biUnion, Finset.mem_univ, Finset.singleton_nonempty

      · let v : Fin n := ⟨0, by omega⟩
        have hne_univ : ({v} : Finset (Fin n)).biUnion (fun u => (⊤ : SimpleGraph (Fin n)).neighborFinset u) ≠ Finset.univ := by
          simp only [Finset.singleton_biUnion]
          intro h
          have : v ∉ (⊤ : SimpleGraph (Fin n)).neighborFinset v := by simp
          rw [h] at this
          exact this (Finset.mem_univ v)
        have : Nonempty { S : Finset (Fin n) // S.Nonempty ∧ S.biUnion (fun u => (⊤ : SimpleGraph (Fin n)).neighborFinset u) ≠ Finset.univ } :=
          ⟨⟨{v}, Finset.singleton_nonempty v, hne_univ⟩⟩
  6. To establish the lower bound, it suffices to show n - 1 ≤ |N(S)| / |S| for an arbitrary candidate subset S.

    By definition, simple_graph_binding_number is the infimum of |N(S)| / |S| over all nonempty subsets S with N(S) ≠ V. By le_ciInf, a number is at most the infimum if it is a lower bound for every candidate S.

    lines 28–31

    uses simple_graph_binding_number, le_ciInf

        dsimp [simple_graph_binding_number]
        apply le_ciInf
        rintro ⟨S, hSne, hSuniv⟩
        change (n : ℝ) - 1 ≤ ((S.biUnion (fun u => (⊤ : SimpleGraph (Fin n)).neighborFinset u)).card : ℝ) / (S.card : ℝ)
  7. Any candidate subset S can contain at most one vertex: all elements in S are equal.

    Suppose for contradiction that S contains two distinct vertices u and w. In a complete graph, every vertex x is adjacent to all other vertices. If x = u, then x ≠ w, so x is adjacent to w ∈ S; if x ≠ u, then x is adjacent to u ∈ S. Thus every vertex in the graph belongs to N(S), meaning N(S) = V, which contradicts the hypothesis that N(S) ≠ V.

    lines 32–43

    uses Finset.mem_biUnion, SimpleGraph.mem_neighborFinset, SimpleGraph.top_adj, Finset.mem_univ, iff_true, Ne.symm

        have hall_eq : ∀ u ∈ S, ∀ w ∈ S, u = w := by
          intro u hu w hw
          by_contra hne
          have huniv : S.biUnion (fun x => (⊤ : SimpleGraph (Fin n)).neighborFinset x) = Finset.univ := by
            ext x
            simp only [Finset.mem_biUnion, SimpleGraph.mem_neighborFinset, SimpleGraph.top_adj, Finset.mem_univ, iff_true]
            by_cases hxu : x = u
            · refine ⟨w, hw, ?_⟩
              rw [hxu]
              exact Ne.symm hne
            · refine ⟨u, hu, Ne.symm hxu⟩
          exact hSuniv huniv
  8. The set S is a singleton {u} for some vertex u.

    Since S is nonempty, it contains some element u. Because any two elements of S are equal, every element in S must equal u, so S = {u}.

    lines 44–50

    uses Finset.mem_singleton

        obtain ⟨u, hu⟩ := hSne
        have hS_eq : S = {u} := by
          ext x
          simp only [Finset.mem_singleton]
          constructor
          · intro hx; exact hall_eq x hx u hu
          · rintro rfl; exact hu
  9. The inequality n - 1 ≤ |N(S)| / |S| holds for S = {u}.

    Substituting S = {u}, the denominator is |{u}| = 1, and the numerator is the cardinality of N(u) = V ∖ {u}, which is n - 1. The ratio is therefore exactly n - 1, satisfying the inequality by reflexivity.

    lines 51–57

    uses Finset.singleton_biUnion, Finset.card_singleton, Nat.cast_one, div_one, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, Fintype.card_fin, Nat.cast_pred, le_of_eq

        rw [hS_eq]
        simp only [Finset.singleton_biUnion, Finset.card_singleton, Nat.cast_one, div_one]
        have hnv : (⊤ : SimpleGraph (Fin n)).neighborFinset u = Finset.univ.erase u := by
          ext x; simp
        rw [hnv, Finset.card_erase_of_mem (Finset.mem_univ u), Finset.card_univ, Fintype.card_fin]
        have : 1 ≤ n := by omega
        exact le_of_eq (Nat.cast_pred this).symm
le_antisymm
If a ≤ b and b ≤ a, then a = b.
simple_graph_binding_number_le_iff
The binding number of G is at most c if and only if there exists a nonempty vertex set S with N(S) ≠ V such that |N(S)| ≤ c · |S|.
Finset.singleton_nonempty
For any element a, the singleton set {a} is nonempty.
Finset.singleton_biUnion
The indexed union over a singleton set {a} evaluates to the set at a: ⋃_{x ∈ {a}} t(x) = t(a).
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.card_singleton
The cardinality of a singleton set {a} is 1.
Nat.cast_one
The natural number 1 cast into a semiring is 1.
mul_one
Multiplying any element by 1 leaves it unchanged: a * 1 = a.
Finset.card_erase_of_mem
Removing an element a from a finite set s containing a decreases its cardinality by 1: |s ∖ {a}| = |s| - 1.
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of that type.
Fintype.card_fin
The cardinality of the standard finite type Fin n is n.
le_of_eq
If a = b, then a ≤ b.
Nat.cast_pred
For n > 0, the real cast of n - 1 equals (n : ℝ) - 1.
simple_graph_binding_number
Definition of the binding number of a simple graph as the infimum of |N(S)| / |S| over all nonempty subsets S with N(S) ≠ V.
le_ciInf
A value c is bounded above by the infimum ⨅ x, f(x) if c ≤ f(x) for all x.
Finset.mem_biUnion
An element b belongs to ⋃_{a ∈ s} t(a) if and only if there exists some a ∈ s such that b ∈ t(a).
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor set of v if and only if v and w are adjacent.
SimpleGraph.top_adj
In the complete graph ⊤, vertices v and w are adjacent if and only if v ≠ w.
iff_true
The equivalence (p ↔ True) simplifies to p.
Ne.symm
If a ≠ b, then b ≠ a.
Finset.mem_singleton
An element b is in the singleton {a} if and only if b = a.
div_one
Dividing any element by 1 leaves it unchanged: a / 1 = a.

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_complete (n : ℕ) (hn : 2 ≤ n) :    simple_graph_binding_number (⊤ : SimpleGraph (Fin n)) = (n : ℝ) - 1 := by  refine le_antisymm ?_ ?_  · have : Nonempty (Fin n) := ⟨⟨0, by omega⟩⟩    rw [simple_graph_binding_number_le_iff]    let v : Fin n := ⟨0, by omega⟩    refine ⟨{v}, Finset.singleton_nonempty v, ?_, ?_⟩    · simp only [Finset.singleton_biUnion]      intro h      have : v ∉ (⊤ : SimpleGraph (Fin n)).neighborFinset v := by simp      rw [h] at this      exact this (Finset.mem_univ v)    · simp only [Finset.singleton_biUnion, Finset.card_singleton, Nat.cast_one, mul_one]      have hnv : (⊤ : SimpleGraph (Fin n)).neighborFinset v = Finset.univ.erase v := by        ext x; simp      rw [hnv, Finset.card_erase_of_mem (Finset.mem_univ v), Finset.card_univ, Fintype.card_fin]      have : 1 ≤ n := by omega      exact le_of_eq (Nat.cast_pred this)  · let v : Fin n := ⟨0, by omega⟩    have hne_univ : ({v} : Finset (Fin n)).biUnion (fun u => (⊤ : SimpleGraph (Fin n)).neighborFinset u) ≠ Finset.univ := by      simp only [Finset.singleton_biUnion]      intro h      have : v ∉ (⊤ : SimpleGraph (Fin n)).neighborFinset v := by simp      rw [h] at this      exact this (Finset.mem_univ v)    have : Nonempty { S : Finset (Fin n) // S.Nonempty ∧ S.biUnion (fun u => (⊤ : SimpleGraph (Fin n)).neighborFinset u) ≠ Finset.univ } :=      ⟨⟨{v}, Finset.singleton_nonempty v, hne_univ⟩⟩    dsimp [simple_graph_binding_number]    apply le_ciInf    rintro ⟨S, hSne, hSuniv⟩    change (n : ℝ) - 1 ≤ ((S.biUnion (fun u => (⊤ : SimpleGraph (Fin n)).neighborFinset u)).card : ℝ) / (S.card : ℝ)    have hall_eq : ∀ u ∈ S, ∀ w ∈ S, u = w := by      intro u hu w hw      by_contra hne      have huniv : S.biUnion (fun x => (⊤ : SimpleGraph (Fin n)).neighborFinset x) = Finset.univ := by        ext x        simp only [Finset.mem_biUnion, SimpleGraph.mem_neighborFinset, SimpleGraph.top_adj, Finset.mem_univ, iff_true]        by_cases hxu : x = u        · refine ⟨w, hw, ?_⟩          rw [hxu]          exact Ne.symm hne        · refine ⟨u, hu, Ne.symm hxu⟩      exact hSuniv huniv    obtain ⟨u, hu⟩ := hSne    have hS_eq : S = {u} := by      ext x      simp only [Finset.mem_singleton]      constructor      · intro hx; exact hall_eq x hx u hu      · rintro rfl; exact hu    rw [hS_eq]    simp only [Finset.singleton_biUnion, Finset.card_singleton, Nat.cast_one, div_one]    have hnv : (⊤ : SimpleGraph (Fin n)).neighborFinset u = Finset.univ.erase u := by      ext x; simp    rw [hnv, Finset.card_erase_of_mem (Finset.mem_univ u), Finset.card_univ, Fintype.card_fin]    have : 1 ≤ n := by omega    exact le_of_eq (Nat.cast_pred this).symm
See it in the graphDiscuss this resultChallenge it