simple_graph_binding_number_complete_four_partite
The 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 K_5-free graphs would be sharp.
Statement
theorem simple_graph_binding_number_complete_four_partite (m : ℕ) (hm : 1 ≤ m) : simple_graph_binding_number (SimpleGraph.completeMultipartiteGraph (fun _ : Fin 4 => Fin m)) = 3 ∧ (SimpleGraph.completeMultipartiteGraph (fun _ : Fin 4 => Fin m)).CliqueFree 5
- Formalizes
- arXiv:2610.28536 (A sharp bound on the binding number of K_k-free graphs and the Brandt conjecture), Sec. 1: the bound k − 2 is attained by complete (k−1)-partite graphs with equal parts (case k = 5)
- 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 theorem establishes that the complete 4-partite graph with parts of size m ≥ 1 is K_5-free and has binding number exactly 3. Any vertex subset S whose neighborhood does not cover the entire graph must be entirely contained in a single part, which implies that |S| ≤ m and its neighborhood comprises all 3m vertices in the other three parts. The ratio |N(S)| / |S| is therefore at least 3m / m = 3, with equality attained when S is an entire part, giving a binding number of 3. Finally, clique-freeness for K_5 follows from the Pigeonhole Principle because a 4-partite graph cannot contain a clique of size 5.
The cardinality of any single part {u | u.1 = i} in the complete 4-partite graph is m.
The set of vertices with part index i is the image of Fin m under the embedding x ↦ (i, x). Using extensionality to equate this filtered finset with the map of Finset.univ, the cardinality equals the size of Fin m, which is m.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_maphave h : (Finset.filter (fun u : (Σ _ : Fin 4, Fin m) => u.1 = i) Finset.univ) = (Finset.univ : Finset (Fin m)).map ⟨fun x => ⟨i, x⟩, fun x y h => by injections⟩ := by ext ⟨a, b⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map] constructor · rintro rfl; exact ⟨b, rfl⟩ · rintro ⟨c, hc⟩; injection hc with h1 h2; exact h1.symm rw [h] simp
The cardinality of the set of vertices outside part i, {u | u.1 ≠ i}, is 3 * m.
The set of vertices outside part i is the complement of part i within the universal set (via Finset.filter_not). Subtracting the size of part i (which is m) from the total number of vertices (which is 4 * m) gives 4 * m - m = 3 * m, closed by omega.
uses
Finset.filter_not,Finset.card_sdiff_of_subset,Finset.filter_subset,simple_graph_binding_number_complete_four_partite_card_filter_eqhave h_not : (Finset.filter (fun u : (Σ _ : Fin 4, Fin m) => u.1 ≠ i) Finset.univ) = Finset.univ \ Finset.filter (fun u : (Σ _ : Fin 4, Fin m) => u.1 = i) Finset.univ := by exact Finset.filter_not (fun u : (Σ _ : Fin 4, Fin m) => u.1 = i) Finset.univ rw [h_not, Finset.card_sdiff_of_subset (Finset.filter_subset _ _)] rw [simple_graph_binding_number_complete_four_partite_card_filter_eq] simp omega
Any subset S whose vertices all belong to part i satisfies |S| ≤ m.
Since every vertex in S has first coordinate i, S is a subset of {u | u.1 = i}. By monotonicity of finset cardinality, |S| is bounded by the size of that part, which is m.
uses
Finset.card_le_card,simple_graph_binding_number_complete_four_partite_card_filter_eqhave h_sub : S ⊆ Finset.filter (fun u => u.1 = i) Finset.univ := by intro v hv simp [hi v hv] have := Finset.card_le_card h_sub rw [simple_graph_binding_number_complete_four_partite_card_filter_eq] at this exact this
If the neighborhood N(S) is not the entire vertex set, then all vertices of S belong to the same part.
Suppose, for contradiction, that S contains vertices from at least two parts, so that for every part index j there is some vertex in S not in part j. For any vertex u in the graph, we can find a vertex v ∈ S in a different part than u; because distinct parts are completely connected, u is adjacent to v, making u ∈ N(S). This implies N(S) is the entire vertex set, contradicting the assumption.
uses
Finset.eq_univ_iff_forall,Finset.mem_biUnion,SimpleGraph.mem_neighborFinsetby_contra! h apply huniv rw [Finset.eq_univ_iff_forall] intro u rw [Finset.mem_biUnion] obtain ⟨v, hvS, hvu⟩ := h u.1 exact ⟨v, hvS, by rwa [SimpleGraph.mem_neighborFinset]⟩
For any nonempty set S whose vertices all belong to part i, its neighborhood N(S) is exactly the set of vertices outside part i.
In a complete multipartite graph, adjacency means having different part coordinates. Since every vertex in S has part coordinate i, every neighbor of S must have a part coordinate different from i. Conversely, since S is nonempty, any vertex u with u.1 ≠ i is adjacent to every vertex in S, so it belongs to N(S).
uses
Finset.mem_biUnion,Finset.mem_filter,Finset.mem_univ,true_and,SimpleGraph.mem_neighborFinset,SimpleGraph.completeMultipartiteGraph,SimpleGraph.comap_adj,SimpleGraph.top_adjext u simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and, SimpleGraph.mem_neighborFinset, SimpleGraph.completeMultipartiteGraph, SimpleGraph.comap_adj, SimpleGraph.top_adj] constructor · rintro ⟨v, hvS, hvu⟩ rw [hi v hvS] at hvu exact hvu.symm · intro hu obtain ⟨v, hvS⟩ := hne exact ⟨v, hvS, by rw [hi v hvS]; exact hu.symm⟩
The vertex set of the complete 4-partite graph is nonempty, and proving the theorem reduces to showing bind(G) ≤ 3, 3 ≤ bind(G), and that G is K_5-free.
Since m ≥ 1, the type Fin m has an element 0, making both Fin m and the vertex type Nonempty. By antisymmetry of ≤, the equality bind(G) = 3 splits into bind(G) ≤ 3 and 3 ≤ bind(G).
uses
le_antisymmhave : Nonempty (Fin m) := ⟨⟨0, hm⟩⟩ have : Nonempty ((_ : Fin 4) × Fin m) := ⟨⟨0, ⟨0, hm⟩⟩⟩ set G := SimpleGraph.completeMultipartiteGraph (fun _ : Fin 4 => Fin m) refine ⟨le_antisymm ?_ ?_, ?_⟩
Part 0 defines a nonempty vertex subset S whose neighborhood consists of all vertices outside part 0.
We choose S = {u | u.1 = 0}. The pair (0, 0) belongs to S, so S is nonempty, and by construction every vertex in S has part index 0. By the earlier neighborhood lemma, N(S) equals the set of all vertices with first coordinate distinct from 0.
uses
simple_graph_binding_number_le_iff,simple_graph_binding_number_complete_four_partite_biUnion_neighborFinset_eq_of_all_fst_eq· rw [simple_graph_binding_number_le_iff] let S : Finset ((_ : Fin 4) × Fin m) := Finset.filter (fun u => u.1 = (0 : Fin 4)) Finset.univ have hS_mem : (⟨0, ⟨0, hm⟩⟩ : (Σ _ : Fin 4, Fin m)) ∈ S := by simp [S] have hSne : S.Nonempty := ⟨⟨0, ⟨0, hm⟩⟩, hS_mem⟩ have hSi : ∀ v ∈ S, v.1 = (0 : Fin 4) := by intro v hv simp only [S, Finset.mem_filter] at hv exact hv.2 have hSN : S.biUnion (fun v => G.neighborFinset v) = Finset.filter (fun u => u.1 ≠ (0 : Fin 4)) Finset.univ := simple_graph_binding_number_complete_four_partite_biUnion_neighborFinset_eq_of_all_fst_eq hSne hSi
The binding number of G is at most 3.
We check the two conditions on S: first, N(S) ≠ univ because the vertex (0, 0) is not in N(S); second, |N(S)| = 3 * m and |S| = m, so |N(S)| ≤ 3 * |S| holds with equality. By simple_graph_binding_number_le_iff, this exhibits S as a witness proving bind(G) ≤ 3.
uses
Finset.mem_univ,simple_graph_binding_number_complete_four_partite_card_filter_ne,simple_graph_binding_number_complete_four_partite_card_filter_eqrefine ⟨S, hSne, ?_, ?_⟩ · rw [hSN] intro h_univ have : (⟨0, ⟨0, hm⟩⟩ : (Σ _ : Fin 4, Fin m)) ∈ Finset.univ := Finset.mem_univ _ rw [← h_univ] at this simp at this · rw [hSN, simple_graph_binding_number_complete_four_partite_card_filter_ne, simple_graph_binding_number_complete_four_partite_card_filter_eq] push_cast linarith
The type of admissible subsets S (nonempty sets with N(S) ≠ univ) is nonempty.
The singleton set {(0, 0)} is nonempty, and because the graph has no self-loops, (0, 0) does not belong to its own neighborhood, so N({(0, 0)}) cannot be the full vertex set.
uses
Finset.singleton_nonempty,Finset.mem_univ· have : Nonempty { S : Finset ((_ : Fin 4) × Fin m) // S.Nonempty ∧ S.biUnion (fun v => G.neighborFinset v) ≠ Finset.univ } := by refine ⟨⟨{⟨0, ⟨0, hm⟩⟩}, Finset.singleton_nonempty _, ?_⟩⟩ intro heq have hnv : (⟨0, ⟨0, hm⟩⟩ : (Σ _ : Fin 4, Fin m)) ∉ ({⟨0, ⟨0, hm⟩⟩} : Finset _).biUnion (fun u => G.neighborFinset u) := by simp rw [heq] at hnv exact hnv (Finset.mem_univ _)
To establish 3 ≤ bind(G), it suffices to show 3 ≤ |N(S)| / |S| for an arbitrary admissible subset S.
By definition, the binding number is the infimum over all nonempty subsets S with N(S) ≠ univ of the ratio |N(S)| / |S|. Since the index set is nonempty, le_ciInf reduces the lower bound 3 ≤ bind(G) to verifying the inequality for every admissible S.
uses
le_ciInfdsimp [simple_graph_binding_number] apply le_ciInf rintro ⟨S, hSne, hSuniv⟩ change 3 ≤ ((S.biUnion (fun v => G.neighborFinset v)).card : ℝ) / S.card
For every admissible subset S, the ratio |N(S)| / |S| is at least 3, so 3 ≤ bind(G).
Since N(S) ≠ univ, all vertices of S share a single part coordinate i. Then N(S) is the set of vertices outside part i, which has cardinality 3 * m, and |S| ≤ m. Since S is nonempty, |S| > 0. The inequality 3 ≤ 3 * m / |S| is equivalent to 3 * |S| ≤ 3 * m, which follows immediately from |S| ≤ m.
uses
simple_graph_binding_number_complete_four_partite_all_fst_eq_of_ne_univ,simple_graph_binding_number_complete_four_partite_biUnion_neighborFinset_eq_of_all_fst_eq,simple_graph_binding_number_complete_four_partite_card_filter_ne,Nat.cast_pos.mpr,Nat.cast_le.mpr,simple_graph_binding_number_complete_four_partite_card_le_of_all_fst_eq,le_div_iff₀obtain ⟨i, hi⟩ := simple_graph_binding_number_complete_four_partite_all_fst_eq_of_ne_univ hSuniv have hSN : S.biUnion (fun v => G.neighborFinset v) = Finset.filter (fun u => u.1 ≠ i) Finset.univ := simple_graph_binding_number_complete_four_partite_biUnion_neighborFinset_eq_of_all_fst_eq hSne hi rw [hSN, simple_graph_binding_number_complete_four_partite_card_filter_ne] have h1 : 0 < (S.card : ℝ) := Nat.cast_pos.mpr hSne.card_pos have h2 : (S.card : ℝ) ≤ (m : ℝ) := Nat.cast_le.mpr (simple_graph_binding_number_complete_four_partite_card_le_of_all_fst_eq hi) rw [le_div_iff₀ h1] push_cast linarith
The complete 4-partite graph is K_5-free.
A complete multipartite graph cannot contain a clique whose size exceeds the number of parts. Since the graph has 4 parts and 4 < 5 (checked by decide), it contains no 5-clique.
uses
SimpleGraph.cliqueFree_completeMultipartiteGraph· apply SimpleGraph.cliqueFree_completeMultipartiteGraph decide
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
true_and- The logical conjunction True ∧ p is equivalent to p.
Finset.mem_map- An element b belongs to the image Finset.map f s of an embedding f if and only if b = f a for some a in s.
Finset.filter_not- Filtering a finset by the negation of a predicate is equal to the set difference of the finset and the set filtered by the predicate.
Finset.card_sdiff_of_subset- If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.filter_subset- The filtered subset Finset.filter p s is a subset of s.
simple_graph_binding_number_complete_four_partite_card_filter_eq- In the vertex set of four parts of size m, the part indexed by i contains exactly m vertices.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Finset.eq_univ_iff_forall- A finset equals the universal finset if and only if it contains every element of the type.
Finset.mem_biUnion- An element belongs to a finset biUnion if and only if it belongs to the image of at least one element of the domain set.
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
SimpleGraph.completeMultipartiteGraph- The complete multipartite graph with vertex set given by a disjoint union of parts, where two vertices are adjacent if and only if they lie in different parts.
SimpleGraph.comap_adj- Two vertices are adjacent in a comap graph under f if and only if their images under f are adjacent.
SimpleGraph.top_adj- Two vertices are adjacent in the complete graph ⊤ if and only if they are distinct.
le_antisymm- If a ≤ b and b ≤ a in a partial order, 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 set S with N(S) ≠ V such that |N(S)| ≤ c * |S|.
simple_graph_binding_number_complete_four_partite_biUnion_neighborFinset_eq_of_all_fst_eq- For a nonempty subset S contained entirely within part i, its neighborhood in the complete multipartite graph equals the set of all vertices outside part i.
simple_graph_binding_number_complete_four_partite_card_filter_ne- The set of all vertices belonging to parts other than i has cardinality 3 * m.
Finset.singleton_nonempty- A singleton finset {a} is nonempty.
le_ciInf- A constant c is at most the infimum of a family f if c ≤ f x for all x in the index set.
simple_graph_binding_number_complete_four_partite_all_fst_eq_of_ne_univ- If the neighborhood of a subset S is not the universal set, then all vertices in S must belong to the same part.
Nat.cast_pos.mpr- If a natural number is strictly positive, its coercion to the real numbers is strictly positive.
Nat.cast_le.mpr- If a ≤ b for natural numbers, then (a : ℝ) ≤ (b : ℝ).
simple_graph_binding_number_complete_four_partite_card_le_of_all_fst_eq- If all vertices in a subset S belong to the same part i, then |S| ≤ m.
le_div_iff₀- For c > 0, a ≤ b / c is equivalent to a * c ≤ b.
SimpleGraph.cliqueFree_completeMultipartiteGraph- A complete multipartite graph with k parts contains no clique of size n whenever k < n.
- The binding number is formalized as a conditional infimum (⨅) over the subtype of nonempty vertex subsets whose neighborhood is not the full vertex set. Applying infimum principles like le_ciInf requires first formally verifying that this subtype is nonempty (which is done using a singleton set).
- Vertices of the complete 4-partite graph are represented as dependent pairs (i, x) in (Σ _ : Fin 4, Fin m), where i : Fin 4 identifies the partite class and x : Fin m identifies the vertex within that class.
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.
lemma simple_graph_binding_number_complete_four_partite_card_filter_eq (m : ℕ) (i : Fin 4) : (Finset.filter (fun u : (Σ _ : Fin 4, Fin m) => u.1 = i) Finset.univ).card = m := by have h : (Finset.filter (fun u : (Σ _ : Fin 4, Fin m) => u.1 = i) Finset.univ) = (Finset.univ : Finset (Fin m)).map ⟨fun x => ⟨i, x⟩, fun x y h => by injections⟩ := by ext ⟨a, b⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map] constructor · rintro rfl; exact ⟨b, rfl⟩ · rintro ⟨c, hc⟩; injection hc with h1 h2; exact h1.symm rw [h] simplemma simple_graph_binding_number_complete_four_partite_card_filter_ne (m : ℕ) (i : Fin 4) : (Finset.filter (fun u : (Σ _ : Fin 4, Fin m) => u.1 ≠ i) Finset.univ).card = 3 * m := by have h_not : (Finset.filter (fun u : (Σ _ : Fin 4, Fin m) => u.1 ≠ i) Finset.univ) = Finset.univ \ Finset.filter (fun u : (Σ _ : Fin 4, Fin m) => u.1 = i) Finset.univ := by exact Finset.filter_not (fun u : (Σ _ : Fin 4, Fin m) => u.1 = i) Finset.univ rw [h_not, Finset.card_sdiff_of_subset (Finset.filter_subset _ _)] rw [simple_graph_binding_number_complete_four_partite_card_filter_eq] simp omegalemma simple_graph_binding_number_complete_four_partite_card_le_of_all_fst_eq {m : ℕ} {S : Finset (Σ _ : Fin 4, Fin m)} {i : Fin 4} (hi : ∀ v ∈ S, v.1 = i) : S.card ≤ m := by have h_sub : S ⊆ Finset.filter (fun u => u.1 = i) Finset.univ := by intro v hv simp [hi v hv] have := Finset.card_le_card h_sub rw [simple_graph_binding_number_complete_four_partite_card_filter_eq] at this exact thislemma simple_graph_binding_number_complete_four_partite_all_fst_eq_of_ne_univ {m : ℕ} {S : Finset (Σ _ : Fin 4, Fin m)} (huniv : S.biUnion (fun v => (SimpleGraph.completeMultipartiteGraph (fun _ : Fin 4 => Fin m)).neighborFinset v) ≠ Finset.univ) : ∃ i : Fin 4, ∀ v ∈ S, v.1 = i := by by_contra! h apply huniv rw [Finset.eq_univ_iff_forall] intro u rw [Finset.mem_biUnion] obtain ⟨v, hvS, hvu⟩ := h u.1 exact ⟨v, hvS, by rwa [SimpleGraph.mem_neighborFinset]⟩lemma simple_graph_binding_number_complete_four_partite_biUnion_neighborFinset_eq_of_all_fst_eq {m : ℕ} {S : Finset (Σ _ : Fin 4, Fin m)} (hne : S.Nonempty) {i : Fin 4} (hi : ∀ v ∈ S, v.1 = i) : S.biUnion (fun v => (SimpleGraph.completeMultipartiteGraph (fun _ : Fin 4 => Fin m)).neighborFinset v) = Finset.filter (fun u => u.1 ≠ i) Finset.univ := by ext u simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and, SimpleGraph.mem_neighborFinset, SimpleGraph.completeMultipartiteGraph, SimpleGraph.comap_adj, SimpleGraph.top_adj] constructor · rintro ⟨v, hvS, hvu⟩ rw [hi v hvS] at hvu exact hvu.symm · intro hu obtain ⟨v, hvS⟩ := hne exact ⟨v, hvS, by rw [hi v hvS]; exact hu.symm⟩theorem simple_graph_binding_number_complete_four_partite (m : ℕ) (hm : 1 ≤ m) : simple_graph_binding_number (SimpleGraph.completeMultipartiteGraph (fun _ : Fin 4 => Fin m)) = 3 ∧ (SimpleGraph.completeMultipartiteGraph (fun _ : Fin 4 => Fin m)).CliqueFree 5 := by have : Nonempty (Fin m) := ⟨⟨0, hm⟩⟩ have : Nonempty ((_ : Fin 4) × Fin m) := ⟨⟨0, ⟨0, hm⟩⟩⟩ set G := SimpleGraph.completeMultipartiteGraph (fun _ : Fin 4 => Fin m) refine ⟨le_antisymm ?_ ?_, ?_⟩ · rw [simple_graph_binding_number_le_iff] let S : Finset ((_ : Fin 4) × Fin m) := Finset.filter (fun u => u.1 = (0 : Fin 4)) Finset.univ have hS_mem : (⟨0, ⟨0, hm⟩⟩ : (Σ _ : Fin 4, Fin m)) ∈ S := by simp [S] have hSne : S.Nonempty := ⟨⟨0, ⟨0, hm⟩⟩, hS_mem⟩ have hSi : ∀ v ∈ S, v.1 = (0 : Fin 4) := by intro v hv simp only [S, Finset.mem_filter] at hv exact hv.2 have hSN : S.biUnion (fun v => G.neighborFinset v) = Finset.filter (fun u => u.1 ≠ (0 : Fin 4)) Finset.univ := simple_graph_binding_number_complete_four_partite_biUnion_neighborFinset_eq_of_all_fst_eq hSne hSi refine ⟨S, hSne, ?_, ?_⟩ · rw [hSN] intro h_univ have : (⟨0, ⟨0, hm⟩⟩ : (Σ _ : Fin 4, Fin m)) ∈ Finset.univ := Finset.mem_univ _ rw [← h_univ] at this simp at this · rw [hSN, simple_graph_binding_number_complete_four_partite_card_filter_ne, simple_graph_binding_number_complete_four_partite_card_filter_eq] push_cast linarith · have : Nonempty { S : Finset ((_ : Fin 4) × Fin m) // S.Nonempty ∧ S.biUnion (fun v => G.neighborFinset v) ≠ Finset.univ } := by refine ⟨⟨{⟨0, ⟨0, hm⟩⟩}, Finset.singleton_nonempty _, ?_⟩⟩ intro heq have hnv : (⟨0, ⟨0, hm⟩⟩ : (Σ _ : Fin 4, Fin m)) ∉ ({⟨0, ⟨0, hm⟩⟩} : Finset _).biUnion (fun u => G.neighborFinset u) := by simp rw [heq] at hnv exact hnv (Finset.mem_univ _) dsimp [simple_graph_binding_number] apply le_ciInf rintro ⟨S, hSne, hSuniv⟩ change 3 ≤ ((S.biUnion (fun v => G.neighborFinset v)).card : ℝ) / S.card obtain ⟨i, hi⟩ := simple_graph_binding_number_complete_four_partite_all_fst_eq_of_ne_univ hSuniv have hSN : S.biUnion (fun v => G.neighborFinset v) = Finset.filter (fun u => u.1 ≠ i) Finset.univ := simple_graph_binding_number_complete_four_partite_biUnion_neighborFinset_eq_of_all_fst_eq hSne hi rw [hSN, simple_graph_binding_number_complete_four_partite_card_filter_ne] have h1 : 0 < (S.card : ℝ) := Nat.cast_pos.mpr hSne.card_pos have h2 : (S.card : ℝ) ≤ (m : ℝ) := Nat.cast_le.mpr (simple_graph_binding_number_complete_four_partite_card_le_of_all_fst_eq hi) rw [le_div_iff₀ h1] push_cast linarith · apply SimpleGraph.cliqueFree_completeMultipartiteGraph decide