simple_graph_binding_number_complete
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.
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.
uses
le_antisymmrefine le_antisymm ?_ ?_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.
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, ?_, ?_⟩
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.
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)
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.
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)
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.
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⟩⟩
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.
uses
simple_graph_binding_number,le_ciInfdsimp [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 : ℝ)
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.
uses
Finset.mem_biUnion,SimpleGraph.mem_neighborFinset,SimpleGraph.top_adj,Finset.mem_univ,iff_true,Ne.symmhave 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
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}.
uses
Finset.mem_singletonobtain ⟨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
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.
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_eqrw [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.
- In Lean, the infimum defining the binding number is indexed over the subtype of nonempty subsets S with N(S) ≠ V, so a preliminary step must show that this subtype is nonempty before applying le_ciInf.
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_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