AFTD Auto-Formalizing Theoretical Domains

b5_cliqueNum

theoremverified

ω(B_5(n_0..n_4)) = n_4 + max(n_0 + n_1, n_1 + n_3, n_2 + n_3).

Statement

theorem b5_cliqueNum (n : Fin 5 → ℕ) :
    (b5_graph n).cliqueNum = n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3)
Source
arXiv:2610.21388 (Stronger spectral bound for clique number), Sec. 2.2 (structural clique number of B_t) for t = 5; serves b5_clique_bound_iff
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • b5_graphThe graph B_5(n_1..n_5) of arXiv:2610.21388: each vertex i of G_5 is replaced by a clique of n_i vertices, and cliques of adjacent…
  • b5_graph_adjSanity lemma: adjacency in B_5 unfolds to: distinct, and the same block or adjacent blocks of G_5.
  • g5_adjG_5 on vertices r_1, r_2, w_1, w_2, r_3 (indices 0..4): edges r_1 r_2, w_1 w_2, r_2 w_2, and r_3 adjacent to all.
Used by 1
  • b5_clique_bound_iffFor B_5(n_0..n_4) with all n_i ≥ 1, the strong spectral clique bound sqrt(Σ_{λ ≠ -1} λ^2) ≤ n(1 - 1/ω) (with Σ_{λ≠-1} λ^2 = tr(M^2) for…

The proof, explained

The graph B₅(n) is obtained from the 5-vertex base graph G₅ by replacing each vertex i with a clique of size n i, connecting vertices in different blocks whenever the corresponding blocks are adjacent in G₅. The maximal cliques of G₅ are {0, 1, 4}, {1, 3, 4}, and {2, 3, 4}, each consisting of the universal apex vertex 4 and an edge of the remaining 4-cycle path. For the lower bound on the clique number ω(B₅(n)), the full union of blocks corresponding to any of these three cliques forms a clique in B₅(n) of size n 0 + n 1 + n 4, n 1 + n 3 + n 4, or n 2 + n 3 + n 4, respectively. For the upper bound, the vertices of any maximum clique in B₅(n) must project to a clique in G₅ and hence are contained in one of these three block unions, so its size cannot exceed the maximum of the three sums. By partial order antisymmetry, the clique number equals n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3).

  1. For any index set T ⊆ Fin 5, the cardinality of the full union of blocks over T is the sum of their sizes, ∑_{i ∈ T} n i.

    Rewriting with `Finset.card_sigma` decomposes the cardinality of the sigma type into the sum of the cardinalities of each fiber `Finset.univ : Finset (Fin (n i))`. Simplification then evaluates each fiber's cardinality to n i.

    lines 1–6

    uses Finset.card_sigma

    /-- Cardinality of a full union of blocks: `Σ_{i ∈ T} n i`. -/
    theorem b5_cliqueNum_card_sigma_univ (n : Fin 5 → ℕ) (T : Finset (Fin 5)) :
        (Finset.sigma T (fun i => (Finset.univ : Finset (Fin (n i))))).card = ∑ i ∈ T, n i := by
      rw [Finset.card_sigma]
      simp
    
  2. The full union of blocks indexed by {0, 1, 4} contains n 0 + n 1 + n 4 vertices.

    Applying the general block union cardinality formula `b5_cliqueNum_card_sigma_univ` rewrites the cardinality as the sum ∑_{i ∈ {0, 1, 4}} n i. Simplification expands this finite sum to n 0 + (n 1 + n 4), and linear integer arithmetic (`omega`) re-associates the terms to n 0 + n 1 + n 4.

    lines 7–14

    uses b5_cliqueNum_card_sigma_univ

    /-- The union of blocks `{0,1,4}` has `n 0 + n 1 + n 4` vertices. -/
    theorem b5_cliqueNum_card_014 (n : Fin 5 → ℕ) :
        (Finset.sigma {0,1,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card
          = n 0 + n 1 + n 4 := by
      rw [b5_cliqueNum_card_sigma_univ]
      simp
      omega
    
  3. The full union of blocks indexed by {1, 3, 4} contains n 1 + n 3 + n 4 vertices.

    By `b5_cliqueNum_card_sigma_univ`, the cardinality is the sum ∑_{i ∈ {1, 3, 4}} n i, which simplifies to n 1 + (n 3 + n 4), and `omega` concludes that this equals n 1 + n 3 + n 4.

    lines 15–22

    uses b5_cliqueNum_card_sigma_univ

    /-- The union of blocks `{1,3,4}` has `n 1 + n 3 + n 4` vertices. -/
    theorem b5_cliqueNum_card_134 (n : Fin 5 → ℕ) :
        (Finset.sigma {1,3,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card
          = n 1 + n 3 + n 4 := by
      rw [b5_cliqueNum_card_sigma_univ]
      simp
      omega
    
  4. The full union of blocks indexed by {2, 3, 4} contains n 2 + n 3 + n 4 vertices.

    By `b5_cliqueNum_card_sigma_univ`, the cardinality is the sum ∑_{i ∈ {2, 3, 4}} n i, simplifying to n 2 + (n 3 + n 4), which `omega` re-associates to n 2 + n 3 + n 4.

    lines 23–30

    uses b5_cliqueNum_card_sigma_univ

    /-- The union of blocks `{2,3,4}` has `n 2 + n 3 + n 4` vertices. -/
    theorem b5_cliqueNum_card_234 (n : Fin 5 → ℕ) :
        (Finset.sigma {2,3,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card
          = n 2 + n 3 + n 4 := by
      rw [b5_cliqueNum_card_sigma_univ]
      simp
      omega
    
  5. Every clique in the base graph G₅ is a subset of {0, 1, 4}, {1, 3, 4}, or {2, 3, 4}. automation

    Since G₅ has only 5 vertices, the property that every pairwise adjacent subset of vertices is contained in {0, 1, 4}, {1, 3, 4}, or {2, 3, 4} is a finite combinatorial statement. Lean's `decide` tactic checks this exhaustively by evaluating the condition on all 2⁵ = 32 subsets.

    lines 31–37

    /-- The cliques of `G₅` are contained in `{0,1,4}`, `{1,3,4}` or `{2,3,4}` (finite check). -/
    theorem b5_cliqueNum_block_subset :
        ∀ A : Finset (Fin 5), (∀ i ∈ A, ∀ j ∈ A, i ≠ j → g5_adj i j) →
          (A ⊆ ({0,1,4} : Finset (Fin 5)) ∨ A ⊆ ({1,3,4} : Finset (Fin 5)) ∨
            A ⊆ ({2,3,4} : Finset (Fin 5))) := by
      decide
    
  6. The full union of blocks indexed by any clique T of G₅ is a clique in B₅(n).

    Take two distinct vertices x and y in the block union over T. By `b5_graph_adj`, they are adjacent in B₅(n) if either their block indices are equal (x.1 = y.1, using `Or.inl`) or their block indices are adjacent in G₅ (using `Or.inr`). A case distinction on whether x.1 = y.1 establishes the claim: if x.1 ≠ y.1, since both block indices belong to T, the hypothesis that T is a clique in G₅ implies that x.1 and y.1 are adjacent in G₅.

    lines 38–48

    uses b5_graph_adj, Or.inl, Or.inr

    /-- The union of any set of pairwise adjacent blocks of `G₅` is a clique of `B_5`. -/
    theorem b5_cliqueNum_sigma_univ_isClique (n : Fin 5 → ℕ) (T : Finset (Fin 5))
        (hT : ∀ i ∈ T, ∀ j ∈ T, i ≠ j → g5_adj i j) :
        (b5_graph n).IsClique ↑(Finset.sigma T (fun i => (Finset.univ : Finset (Fin (n i))))) := by
      intro x hx y hy hxy
      rw [b5_graph_adj]
      refine ⟨hxy, ?_⟩
      by_cases h : x.1 = y.1
      · exact Or.inl h
      · exact Or.inr (hT x.1 (Finset.mem_sigma.1 hx).1 y.1 (Finset.mem_sigma.1 hy).1 h)
    
  7. To prove the clique number formula, it suffices to prove both inequalities, and the upper bound reduces to bounding the size of a maximum clique s.

    The equality is split into two inequalities using partial order antisymmetry (`le_antisymm`). For the upper bound, we obtain a maximum clique s whose cardinality equals the clique number ω(B₅(n)), reducing the goal to showing |s| ≤ n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3).

    lines 49–53

    uses le_antisymm

    theorem b5_cliqueNum (n : Fin 5 → ℕ) :
        (b5_graph n).cliqueNum = n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by
      apply le_antisymm
      · obtain ⟨s, hs⟩ := (b5_graph n).exists_isNClique_cliqueNum
        rw [← hs.card_eq]
  8. The projection of the maximum clique s to the block indices {x.1 | x ∈ s} forms a clique in G₅.

    Let i ≠ j be two distinct block indices in the projection of s, with witnesses x, y ∈ s having x.1 = i and y.1 = j. Because i ≠ j, x and y are distinct. Since s is a clique, x and y are adjacent in B₅(n). By `b5_graph_adj`, this adjacency means x.1 = y.1 or g5_adj x.1 y.1. Since x.1 = y.1 contradicts i ≠ j, the only possibility is that g5_adj i j holds.

    lines 54–63

    uses b5_graph_adj

        have hclique : ∀ i ∈ s.image (fun x => x.1), ∀ j ∈ s.image (fun x => x.1),
            i ≠ j → g5_adj i j := by
          intro i hi j hj hij
          obtain ⟨x, hx, rfl⟩ := Finset.mem_image.1 hi
          obtain ⟨y, hy, rfl⟩ := Finset.mem_image.1 hj
          have hxy : x ≠ y := by rintro rfl; exact hij rfl
          have h := (b5_graph_adj n x y).1 (hs.isClique hx hy hxy)
          rcases h.2 with h' | h'
          · exact absurd h' hij
          · exact h'
  9. When the block projection of s is contained in {0, 1, 4}, |s| is bounded by the desired formula.

    Using `b5_cliqueNum_block_subset`, we perform a three-way case analysis on the projection of s. In the first case where the projection is a subset of {0, 1, 4}, every element x ∈ s has x.1 ∈ {0, 1, 4} and x.2 ∈ Finset.univ (`Finset.mem_univ`), so s is a subset of the full block union over {0, 1, 4}. By monotonicity of cardinality (`Finset.card_le_card`), |s| is bounded by the cardinality of that union, which is n 0 + n 1 + n 4 by `b5_cliqueNum_card_014`. Linear arithmetic (`omega`) confirms n 0 + n 1 + n 4 ≤ n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3).

    lines 64–70

    uses b5_cliqueNum_block_subset, Finset.mem_univ, Finset.card_le_card, b5_cliqueNum_card_014

        rcases b5_cliqueNum_block_subset (s.image fun x => x.1) hclique with h014 | h134 | h234
        · have hsub : s ⊆ Finset.sigma {0,1,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by
            intro x hx
            exact Finset.mem_sigma.2 ⟨h014 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩
          calc s.card ≤ _ := Finset.card_le_card hsub
            _ = n 0 + n 1 + n 4 := b5_cliqueNum_card_014 n
            _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega
  10. When the block projection of s is contained in {1, 3, 4}, |s| is bounded by the desired formula.

    In the second case of the projection case split, s is a subset of the full block union over {1, 3, 4} (since x.2 ∈ Finset.univ by `Finset.mem_univ`). Monotonicity of cardinality (`Finset.card_le_card`) and the size formula `b5_cliqueNum_card_134` give |s| ≤ n 1 + n 3 + n 4. Linear arithmetic (`omega`) verifies that this is at most n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3).

    lines 71–76

    uses Finset.mem_univ, Finset.card_le_card, b5_cliqueNum_card_134

        · have hsub : s ⊆ Finset.sigma {1,3,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by
            intro x hx
            exact Finset.mem_sigma.2 ⟨h134 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩
          calc s.card ≤ _ := Finset.card_le_card hsub
            _ = n 1 + n 3 + n 4 := b5_cliqueNum_card_134 n
            _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega
  11. When the block projection of s is contained in {2, 3, 4}, |s| is bounded by the desired formula.

    In the third case, s is contained in the block union over {2, 3, 4} (`Finset.mem_univ`). By `Finset.card_le_card` and `b5_cliqueNum_card_234`, |s| ≤ n 2 + n 3 + n 4. Linear arithmetic (`omega`) shows this is at most n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3).

    lines 77–82

    uses Finset.mem_univ, Finset.card_le_card, b5_cliqueNum_card_234

        · have hsub : s ⊆ Finset.sigma {2,3,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by
            intro x hx
            exact Finset.mem_sigma.2 ⟨h234 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩
          calc s.card ≤ _ := Finset.card_le_card hsub
            _ = n 2 + n 3 + n 4 := b5_cliqueNum_card_234 n
            _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega
  12. The lower bound n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3) ≤ ω(B₅(n)) holds.

    The sets {0, 1, 4}, {1, 3, 4}, and {2, 3, 4} are pairwise adjacent in G₅ (verified by `decide`), so by `b5_cliqueNum_sigma_univ_isClique`, each of their full block unions forms a clique in B₅(n), whose cardinality is at most the clique number. Using the cardinality formulas `b5_cliqueNum_card_014`, `b5_cliqueNum_card_134`, and `b5_cliqueNum_card_234`, this yields n 0 + n 1 + n 4 ≤ ω(B₅(n)), n 1 + n 3 + n 4 ≤ ω(B₅(n)), and n 2 + n 3 + n 4 ≤ ω(B₅(n)). Finally, linear arithmetic with max (`omega`) combines these three bounds to conclude that n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3) ≤ ω(B₅(n)).

    lines 83–89

    uses b5_cliqueNum_sigma_univ_isClique, b5_cliqueNum_card_014, b5_cliqueNum_card_134, b5_cliqueNum_card_234

      · have h1 := (b5_cliqueNum_sigma_univ_isClique n {0,1,4} (by decide)).card_le_cliqueNum
        have h2 := (b5_cliqueNum_sigma_univ_isClique n {1,3,4} (by decide)).card_le_cliqueNum
        have h3 := (b5_cliqueNum_sigma_univ_isClique n {2,3,4} (by decide)).card_le_cliqueNum
        rw [b5_cliqueNum_card_014 n] at h1
        rw [b5_cliqueNum_card_134 n] at h2
        rw [b5_cliqueNum_card_234 n] at h3
        omega
Finset.card_sigma
The cardinality of a dependent sum (disjoint union) of finite sets is the sum of the cardinalities of the fibers over the indexing set.
b5_cliqueNum_card_sigma_univ
For any set of block indices T, the cardinality of the full union of the corresponding blocks is the sum of their sizes, ∑_{i ∈ T} n i.
b5_graph_adj
Two distinct vertices x and y in B₅(n) are adjacent if and only if they belong to the same block or their respective blocks are adjacent in G₅.
Or.inl
From a proof of proposition a, infers the disjunction a ∨ b.
Or.inr
From a proof of proposition b, infers the disjunction a ∨ b.
le_antisymm
In a partially ordered set, if a ≤ b and b ≤ a, then a = b.
b5_cliqueNum_block_subset
Every clique of vertices in the 5-vertex base graph G₅ is contained in at least one of the three sets {0, 1, 4}, {1, 3, 4}, or {2, 3, 4}.
Finset.mem_univ
Every element of a finite type belongs to the universal finset of that type.
Finset.card_le_card
If a finite set s is a subset of a finite set t, then the cardinality of s is at most the cardinality of t.
b5_cliqueNum_card_014
The full union of the blocks indexed by {0, 1, 4} has exactly n 0 + n 1 + n 4 vertices.
b5_cliqueNum_card_134
The full union of the blocks indexed by {1, 3, 4} has exactly n 1 + n 3 + n 4 vertices.
b5_cliqueNum_card_234
The full union of the blocks indexed by {2, 3, 4} has exactly n 2 + n 3 + n 4 vertices.
b5_cliqueNum_sigma_univ_isClique
If T is a set of pairwise adjacent vertices in G₅, then the full union of the blocks indexed by T forms a clique in B₅(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

/-- Cardinality of a full union of blocks: `Σ_{i ∈ T} n i`. -/theorem b5_cliqueNum_card_sigma_univ (n : Fin 5 → ℕ) (T : Finset (Fin 5)) :    (Finset.sigma T (fun i => (Finset.univ : Finset (Fin (n i))))).card = ∑ i ∈ T, n i := by  rw [Finset.card_sigma]  simp/-- The union of blocks `{0,1,4}` has `n 0 + n 1 + n 4` vertices. -/theorem b5_cliqueNum_card_014 (n : Fin 5 → ℕ) :    (Finset.sigma {0,1,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card      = n 0 + n 1 + n 4 := by  rw [b5_cliqueNum_card_sigma_univ]  simp  omega/-- The union of blocks `{1,3,4}` has `n 1 + n 3 + n 4` vertices. -/theorem b5_cliqueNum_card_134 (n : Fin 5 → ℕ) :    (Finset.sigma {1,3,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card      = n 1 + n 3 + n 4 := by  rw [b5_cliqueNum_card_sigma_univ]  simp  omega/-- The union of blocks `{2,3,4}` has `n 2 + n 3 + n 4` vertices. -/theorem b5_cliqueNum_card_234 (n : Fin 5 → ℕ) :    (Finset.sigma {2,3,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card      = n 2 + n 3 + n 4 := by  rw [b5_cliqueNum_card_sigma_univ]  simp  omega/-- The cliques of `G₅` are contained in `{0,1,4}`, `{1,3,4}` or `{2,3,4}` (finite check). -/theorem b5_cliqueNum_block_subset :    ∀ A : Finset (Fin 5), (∀ i ∈ A, ∀ j ∈ A, i ≠ j → g5_adj i j) →      (A ⊆ ({0,1,4} : Finset (Fin 5)) ∨ A ⊆ ({1,3,4} : Finset (Fin 5)) ∨        A ⊆ ({2,3,4} : Finset (Fin 5))) := by  decide/-- The union of any set of pairwise adjacent blocks of `G₅` is a clique of `B_5`. -/theorem b5_cliqueNum_sigma_univ_isClique (n : Fin 5 → ℕ) (T : Finset (Fin 5))    (hT : ∀ i ∈ T, ∀ j ∈ T, i ≠ j → g5_adj i j) :    (b5_graph n).IsClique ↑(Finset.sigma T (fun i => (Finset.univ : Finset (Fin (n i))))) := by  intro x hx y hy hxy  rw [b5_graph_adj]  refine ⟨hxy, ?_⟩  by_cases h : x.1 = y.1  · exact Or.inl h  · exact Or.inr (hT x.1 (Finset.mem_sigma.1 hx).1 y.1 (Finset.mem_sigma.1 hy).1 h)theorem b5_cliqueNum (n : Fin 5 → ℕ) :    (b5_graph n).cliqueNum = n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by  apply le_antisymm  · obtain ⟨s, hs⟩ := (b5_graph n).exists_isNClique_cliqueNum    rw [← hs.card_eq]    have hclique : ∀ i ∈ s.image (fun x => x.1), ∀ j ∈ s.image (fun x => x.1),        i ≠ j → g5_adj i j := by      intro i hi j hj hij      obtain ⟨x, hx, rfl⟩ := Finset.mem_image.1 hi      obtain ⟨y, hy, rfl⟩ := Finset.mem_image.1 hj      have hxy : x ≠ y := by rintro rfl; exact hij rfl      have h := (b5_graph_adj n x y).1 (hs.isClique hx hy hxy)      rcases h.2 with h' | h'      · exact absurd h' hij      · exact h'    rcases b5_cliqueNum_block_subset (s.image fun x => x.1) hclique with h014 | h134 | h234    · have hsub : s ⊆ Finset.sigma {0,1,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by        intro x hx        exact Finset.mem_sigma.2 ⟨h014 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩      calc s.card ≤ _ := Finset.card_le_card hsub        _ = n 0 + n 1 + n 4 := b5_cliqueNum_card_014 n        _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega    · have hsub : s ⊆ Finset.sigma {1,3,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by        intro x hx        exact Finset.mem_sigma.2 ⟨h134 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩      calc s.card ≤ _ := Finset.card_le_card hsub        _ = n 1 + n 3 + n 4 := b5_cliqueNum_card_134 n        _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega    · have hsub : s ⊆ Finset.sigma {2,3,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by        intro x hx        exact Finset.mem_sigma.2 ⟨h234 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩      calc s.card ≤ _ := Finset.card_le_card hsub        _ = n 2 + n 3 + n 4 := b5_cliqueNum_card_234 n        _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega  · have h1 := (b5_cliqueNum_sigma_univ_isClique n {0,1,4} (by decide)).card_le_cliqueNum    have h2 := (b5_cliqueNum_sigma_univ_isClique n {1,3,4} (by decide)).card_le_cliqueNum    have h3 := (b5_cliqueNum_sigma_univ_isClique n {2,3,4} (by decide)).card_le_cliqueNum    rw [b5_cliqueNum_card_014 n] at h1    rw [b5_cliqueNum_card_134 n] at h2    rw [b5_cliqueNum_card_234 n] at h3    omega
See it in the graphDiscuss this resultChallenge it