AFTD Auto-Formalizing Theoretical Domains

simple_graph_binding_number_complete_four_partite

theoremverifiedformalization

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.

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

    lines 3–11

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map

      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]
      simp
  2. 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.

    lines 15–21

    uses Finset.filter_not, Finset.card_sdiff_of_subset, Finset.filter_subset, simple_graph_binding_number_complete_four_partite_card_filter_eq

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

    lines 25–30

    uses Finset.card_le_card, simple_graph_binding_number_complete_four_partite_card_filter_eq

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

    lines 35–41

    uses Finset.eq_univ_iff_forall, Finset.mem_biUnion, SimpleGraph.mem_neighborFinset

      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]⟩
  5. 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).

    lines 47–56

    uses Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and, SimpleGraph.mem_neighborFinset, SimpleGraph.completeMultipartiteGraph, SimpleGraph.comap_adj, SimpleGraph.top_adj

      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⟩
  6. 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).

    lines 62–65

    uses le_antisymm

      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 ?_ ?_, ?_⟩
  7. 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.

    lines 66–75

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

    lines 76–85

    uses Finset.mem_univ, simple_graph_binding_number_complete_four_partite_card_filter_ne, simple_graph_binding_number_complete_four_partite_card_filter_eq

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

    lines 86–91

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

    lines 92–95

    uses le_ciInf

        dsimp [simple_graph_binding_number]
        apply le_ciInf
        rintro ⟨S, hSne, hSuniv⟩
        change 3 ≤ ((S.biUnion (fun v => G.neighborFinset v)).card : ℝ) / S.card
  11. 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.

    lines 96–104

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

    lines 105–106

    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.

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

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