AFTD Auto-Formalizing Theoretical Domains

b4_cliqueNum

theoremverifiedformalization

The clique number of B_4(n_0, n_1, n_2, n_3) is max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).

Statement

theorem b4_cliqueNum (n : Fin 4 → ℕ) :
    (b4_graph n).cliqueNum = max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3)
Formalizes
arXiv:2610.21388, Section 2.2
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • b4_graphThe graph B_4(n_0, n_1, n_2, n_3) on the disjoint union of four complete blocks of sizes n_0, n_1, n_2, n_3, with edges between blocks 0…
  • b4_graph_adjSanity lemma: two distinct vertices in B_4(n) are adjacent if and only if they belong to the same block, or one is in block 0 and the…
Used by 2

Read back from the Lean

For every function $n : \text{Fin } 4 \to \mathbb{N}$, the clique number of the simple graph b4_graph n is equal to $\max(\max(n(0) + n(1), n(1) + n(3)), n(2) + n(3))$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The graph B_4(n) is formed by four parts where each part is a clique and the edges between parts form the path 0 - 1 - 3 - 2. Since this 4-vertex path contains no triangles, any clique in B_4(n) can only intersect parts that form an edge of the path, namely {0, 1}, {1, 3}, or {2, 3}. A case analysis shows that any clique is contained in one of these three pair blocks, bounding its size by max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3), while each pair block provides a matching lower bound clique of size n_a + n_b.

  1. The cardinality of the pair block of two distinct parts a and b is n(a) + n(b).

    The pair block is defined as a sigma-finset over the pair {a, b}. Its cardinality is the sum of the cardinalities of the two fibers, which simplifies to n(a) + n(b) because a ≠ b.

    lines 8–9

    uses b4_cliqueNum_pairBlock, card_sigma

      rw [b4_cliqueNum_pairBlock, card_sigma]
      simp [hab]
  2. A vertex belongs to the pair block of a and b if and only if its part index is a or b.

    By definition of the sigma-finset over {a, b}, a vertex (i, x) belongs to the block precisely when i ∈ {a, b}, which simplifies to i = a ∨ i = b.

    line 13

    uses b4_cliqueNum_pairBlock

      simp [b4_cliqueNum_pairBlock]
  3. The pair block of parts 0 and 1 forms a clique in B_4(n).

    For any two distinct vertices in parts 0 and 1, their part indices are each 0 or 1. In all four cases, the vertices either share the same part index or belong to the adjacent parts 0 and 1, both of which satisfy the adjacency condition for B_4(n).

    lines 17–25

    uses b4_graph_adj

      intro x hx y hy hne
      simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy
      rw [b4_graph_adj]
      refine ⟨hne, ?_⟩
      rcases hx with hx | hx <;> rcases hy with hy | hy
      · left; rw [hx, hy]
      · right; left; exact ⟨hx, hy⟩
      · right; right; left; exact ⟨hx, hy⟩
      · left; rw [hx, hy]
  4. The pair block of parts 1 and 3 forms a clique in B_4(n).

    Any two distinct vertices whose indices belong to {1, 3} either share a part index or form the pair {1, 3}, which is an edge in the underlying path of parts; thus they are adjacent in B_4(n).

    lines 29–37

    uses b4_graph_adj

      intro x hx y hy hne
      simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy
      rw [b4_graph_adj]
      refine ⟨hne, ?_⟩
      rcases hx with hx | hx <;> rcases hy with hy | hy
      · left; rw [hx, hy]
      · right; right; right; left; exact ⟨hx, hy⟩
      · right; right; right; right; left; exact ⟨hx, hy⟩
      · left; rw [hx, hy]
  5. The pair block of parts 2 and 3 forms a clique in B_4(n).

    Any two distinct vertices whose indices belong to {2, 3} are either in the same part or in the adjacent parts 2 and 3, and are therefore adjacent.

    lines 41–49

    uses b4_graph_adj

      intro x hx y hy hne
      simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy
      rw [b4_graph_adj]
      refine ⟨hne, ?_⟩
      rcases hx with hx | hx <;> rcases hy with hy | hy
      · left; rw [hx, hy]
      · right; right; right; right; right; left; exact ⟨hx, hy⟩
      · right; right; right; right; right; right; exact ⟨hx, hy⟩
      · left; rw [hx, hy]
  6. Any clique containing a vertex from part 0 is a subset of the pair block of parts 0 and 1.

    Let x be a clique vertex in part 0. Any other vertex y in the clique is distinct from x and therefore adjacent to x. Unfolding the definition of adjacency shows that part 0 is only adjacent to itself and part 1. Hence every vertex y in the clique has part index 0 or 1.

    lines 55–71

    uses b4_cliqueNum_mem_pairBlock_iff, b4_graph_adj

      intro y hy
      rw [b4_cliqueNum_mem_pairBlock_iff]
      by_cases hy0 : y.1 = 0
      · left; exact hy0
      · right
        have hne : x ≠ y := by
          intro h; subst h; exact hy0 hx0
        have hadj := hc hx hy hne
        rw [b4_graph_adj] at hadj
        rcases hadj.2 with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩
        · rw [hx0] at h; exact (hy0 h.symm).elim
        · exact h2
        · rw [hx0] at h1; contradiction
        · rw [hx0] at h1; contradiction
        · rw [hx0] at h1; contradiction
        · rw [hx0] at h1; contradiction
        · rw [hx0] at h1; contradiction
  7. Any clique with no vertices in part 0 that contains a vertex from part 1 is a subset of the pair block of parts 1 and 3.

    Let x be a clique vertex in part 1. Every distinct vertex y in the clique must be adjacent to x, so y's part index can only be 0, 1, or 3. Since the clique contains no vertex in part 0 by hypothesis, y must belong to part 1 or part 3.

    lines 78–95

    uses b4_cliqueNum_mem_pairBlock_iff, b4_graph_adj

      intro y hy
      rw [b4_cliqueNum_mem_pairBlock_iff]
      by_cases hy1 : y.1 = 1
      · left; exact hy1
      · right
        have hne : x ≠ y := by
          intro h; subst h; exact hy1 hx1
        have hadj := hc hx hy hne
        rw [b4_graph_adj] at hadj
        have hy0 : y.1 ≠ 0 := h_no_0 y hy
        rcases hadj.2 with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩
        · rw [hx1] at h; exact (hy1 h.symm).elim
        · rw [hx1] at h1; contradiction
        · rw [h2] at hy0; contradiction
        · exact h2
        · rw [hx1] at h1; contradiction
        · rw [hx1] at h1; contradiction
        · rw [hx1] at h1; contradiction
  8. Any clique containing no vertices from parts 0 or 1 is a subset of the pair block of parts 2 and 3. automation

    Every vertex y in the clique has a part index in {0, 1, 2, 3}. Since indices 0 and 1 are excluded by hypothesis, linear arithmetic over Fin 4 leaves only 2 and 3 as possible values.

    lines 101–105

    uses b4_cliqueNum_mem_pairBlock_iff

      intro y hy
      rw [b4_cliqueNum_mem_pairBlock_iff]
      have hy0 := h_no_0 y hy
      have hy1 := h_no_1 y hy
      omega
  9. Every clique s has cardinality at most max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).

    We case-split on which parts meet s: if s meets part 0, then s ⊆ pairBlock(0, 1) and |s| ≤ n_0 + n_1; if s avoids part 0 but meets part 1, then s ⊆ pairBlock(1, 3) and |s| ≤ n_1 + n_3; otherwise s avoids parts 0 and 1, so s ⊆ pairBlock(2, 3) and |s| ≤ n_2 + n_3. In all three cases, |s| is bounded by the maximum of the three sums.

    lines 110–127

    uses b4_cliqueNum_card_pairBlock, b4_cliqueNum_case_0, b4_cliqueNum_case_1, b4_cliqueNum_case_23, card_le_card, le_max_left, le_max_of_le_left, le_max_right, le_trans

      by_cases h0 : ∃ x ∈ s, (x : Σ i : Fin 4, Fin (n i)).1 = 0
      · rcases h0 with ⟨x, hx, hx0⟩
        have hsub := b4_cliqueNum_case_0 n s hc x hx hx0
        have hle := card_le_card hsub
        rw [b4_cliqueNum_card_pairBlock n 0 1 (by decide)] at hle
        exact le_trans hle (le_max_of_le_left (le_max_left _ _))
      · push Not at h0
        by_cases h1 : ∃ x ∈ s, (x : Σ i : Fin 4, Fin (n i)).1 = 1
        · rcases h1 with ⟨x, hx, hx1⟩
          have hsub := b4_cliqueNum_case_1 n s hc h0 x hx hx1
          have hle := card_le_card hsub
          rw [b4_cliqueNum_card_pairBlock n 1 3 (by decide)] at hle
          exact le_trans hle (le_max_of_le_left (le_max_right _ _))
        · push Not at h1
          have hsub := b4_cliqueNum_case_23 n s h0 h1
          have hle := card_le_card hsub
          rw [b4_cliqueNum_card_pairBlock n 2 3 (by decide)] at hle
          exact le_trans hle (le_max_right _ _)
  10. The clique number of B_4(n) is at most max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).

    By definition of the clique number, there exists a maximum clique s with |s| = cliqueNum. Applying the clique size bound to s yields the upper bound on the clique number.

    lines 132–136

    uses b4_cliqueNum_card_le_of_isClique, isNClique_iff, le_antisymm

      apply le_antisymm
      · obtain ⟨s, hs⟩ := (b4_graph n).exists_isNClique_cliqueNum
        rw [isNClique_iff] at hs
        rw [← hs.2]
        exact b4_cliqueNum_card_le_of_isClique n s hs.1
  11. The clique number of B_4(n) equals max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).

    The three pair blocks {0, 1}, {1, 3}, and {2, 3} are explicit cliques of sizes n_0 + n_1, n_1 + n_3, and n_2 + n_3, so each sum is at most the clique number. Their maximum is therefore also at most the clique number. Combined with the upper bound via antisymmetry, the clique number equals this maximum.

    lines 137–146

    uses b4_cliqueNum_card_pairBlock, b4_cliqueNum_isClique_01, b4_cliqueNum_isClique_13, b4_cliqueNum_isClique_23, max_le

      · have h01 : n 0 + n 1 ≤ (b4_graph n).cliqueNum := by
          have := (b4_cliqueNum_isClique_01 n).card_le_cliqueNum
          rwa [b4_cliqueNum_card_pairBlock n 0 1 (by decide)] at this
        have h13 : n 1 + n 3 ≤ (b4_graph n).cliqueNum := by
          have := (b4_cliqueNum_isClique_13 n).card_le_cliqueNum
          rwa [b4_cliqueNum_card_pairBlock n 1 3 (by decide)] at this
        have h23 : n 2 + n 3 ≤ (b4_graph n).cliqueNum := by
          have := (b4_cliqueNum_isClique_23 n).card_le_cliqueNum
          rwa [b4_cliqueNum_card_pairBlock n 2 3 (by decide)] at this
        exact max_le (max_le h01 h13) h23
b4_cliqueNum_pairBlock
The Finset of all vertices belonging to part a or part b.
card_sigma
The cardinality of a disjoint union of finite sets indexed by a Finset is the sum of their cardinalities.
b4_graph_adj
Two vertices in B_4(n) are adjacent if and only if they are distinct and either belong to the same part or to parts adjacent in the path 0-1-3-2.
b4_cliqueNum_mem_pairBlock_iff
A vertex belongs to the pair block of a and b if and only if its part index is a or b.
b4_cliqueNum_case_0
Any clique containing a vertex from part 0 is a subset of the pair block of parts 0 and 1.
card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
b4_cliqueNum_card_pairBlock
For distinct parts a and b, the pair block of a and b has cardinality n(a) + n(b).
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
le_max_of_le_left
If a ≤ b, then a ≤ max(b, c).
le_max_left
For any a and b, a ≤ max(a, b).
b4_cliqueNum_case_1
Any clique with no vertices in part 0 that contains a vertex from part 1 is a subset of the pair block of parts 1 and 3.
le_max_right
For any a and b, b ≤ max(a, b).
b4_cliqueNum_case_23
Any clique with no vertices in parts 0 or 1 is a subset of the pair block of parts 2 and 3.
le_antisymm
If a ≤ b and b ≤ a, then a = b.
isNClique_iff
A set is an n-clique if and only if it is a clique and its cardinality is n.
b4_cliqueNum_card_le_of_isClique
Any clique in B_4(n) has cardinality at most max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).
b4_cliqueNum_isClique_01
The pair block of parts 0 and 1 forms a clique in B_4(n).
b4_cliqueNum_isClique_13
The pair block of parts 1 and 3 forms a clique in B_4(n).
b4_cliqueNum_isClique_23
The pair block of parts 2 and 3 forms a clique in B_4(n).
max_le
If a ≤ c and b ≤ c, then max(a, b) ≤ c.

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

open SimpleGraph Finsetdef b4_cliqueNum_pairBlock (n : Fin 4 → ℕ) (a b : Fin 4) : Finset (Σ i : Fin 4, Fin (n i)) :=  ({a, b} : Finset (Fin 4)).sigma (fun _ => univ)lemma b4_cliqueNum_card_pairBlock (n : Fin 4 → ℕ) (a b : Fin 4) (hab : a ≠ b) :    (b4_cliqueNum_pairBlock n a b).card = n a + n b := by  rw [b4_cliqueNum_pairBlock, card_sigma]  simp [hab]lemma b4_cliqueNum_mem_pairBlock_iff (n : Fin 4 → ℕ) (a b : Fin 4) (x : Σ i : Fin 4, Fin (n i)) :    x ∈ b4_cliqueNum_pairBlock n a b ↔ x.1 = a ∨ x.1 = b := by  simp [b4_cliqueNum_pairBlock]lemma b4_cliqueNum_isClique_01 (n : Fin 4 → ℕ) :    (b4_graph n).IsClique (b4_cliqueNum_pairBlock n 0 1 : Set (Σ i : Fin 4, Fin (n i))) := by  intro x hx y hy hne  simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy  rw [b4_graph_adj]  refine ⟨hne, ?_⟩  rcases hx with hx | hx <;> rcases hy with hy | hy  · left; rw [hx, hy]  · right; left; exact ⟨hx, hy⟩  · right; right; left; exact ⟨hx, hy⟩  · left; rw [hx, hy]lemma b4_cliqueNum_isClique_13 (n : Fin 4 → ℕ) :    (b4_graph n).IsClique (b4_cliqueNum_pairBlock n 1 3 : Set (Σ i : Fin 4, Fin (n i))) := by  intro x hx y hy hne  simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy  rw [b4_graph_adj]  refine ⟨hne, ?_⟩  rcases hx with hx | hx <;> rcases hy with hy | hy  · left; rw [hx, hy]  · right; right; right; left; exact ⟨hx, hy⟩  · right; right; right; right; left; exact ⟨hx, hy⟩  · left; rw [hx, hy]lemma b4_cliqueNum_isClique_23 (n : Fin 4 → ℕ) :    (b4_graph n).IsClique (b4_cliqueNum_pairBlock n 2 3 : Set (Σ i : Fin 4, Fin (n i))) := by  intro x hx y hy hne  simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy  rw [b4_graph_adj]  refine ⟨hne, ?_⟩  rcases hx with hx | hx <;> rcases hy with hy | hy  · left; rw [hx, hy]  · right; right; right; right; right; left; exact ⟨hx, hy⟩  · right; right; right; right; right; right; exact ⟨hx, hy⟩  · left; rw [hx, hy]lemma b4_cliqueNum_case_0 (n : Fin 4 → ℕ) (s : Finset (Σ i : Fin 4, Fin (n i)))    (hc : (b4_graph n).IsClique (s : Set (Σ i : Fin 4, Fin (n i))))    (x : Σ i : Fin 4, Fin (n i)) (hx : x ∈ s) (hx0 : x.1 = 0) :    s ⊆ b4_cliqueNum_pairBlock n 0 1 := by  intro y hy  rw [b4_cliqueNum_mem_pairBlock_iff]  by_cases hy0 : y.1 = 0  · left; exact hy0  · right    have hne : x ≠ y := by      intro h; subst h; exact hy0 hx0    have hadj := hc hx hy hne    rw [b4_graph_adj] at hadj    rcases hadj.2 with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩    · rw [hx0] at h; exact (hy0 h.symm).elim    · exact h2    · rw [hx0] at h1; contradiction    · rw [hx0] at h1; contradiction    · rw [hx0] at h1; contradiction    · rw [hx0] at h1; contradiction    · rw [hx0] at h1; contradictionlemma b4_cliqueNum_case_1 (n : Fin 4 → ℕ) (s : Finset (Σ i : Fin 4, Fin (n i)))    (hc : (b4_graph n).IsClique (s : Set (Σ i : Fin 4, Fin (n i))))    (h_no_0 : ∀ z ∈ s, z.1 ≠ 0)    (x : Σ i : Fin 4, Fin (n i)) (hx : x ∈ s) (hx1 : x.1 = 1) :    s ⊆ b4_cliqueNum_pairBlock n 1 3 := by  intro y hy  rw [b4_cliqueNum_mem_pairBlock_iff]  by_cases hy1 : y.1 = 1  · left; exact hy1  · right    have hne : x ≠ y := by      intro h; subst h; exact hy1 hx1    have hadj := hc hx hy hne    rw [b4_graph_adj] at hadj    have hy0 : y.1 ≠ 0 := h_no_0 y hy    rcases hadj.2 with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩    · rw [hx1] at h; exact (hy1 h.symm).elim    · rw [hx1] at h1; contradiction    · rw [h2] at hy0; contradiction    · exact h2    · rw [hx1] at h1; contradiction    · rw [hx1] at h1; contradiction    · rw [hx1] at h1; contradictionlemma b4_cliqueNum_case_23 (n : Fin 4 → ℕ) (s : Finset (Σ i : Fin 4, Fin (n i)))    (h_no_0 : ∀ z ∈ s, z.1 ≠ 0)    (h_no_1 : ∀ z ∈ s, z.1 ≠ 1) :    s ⊆ b4_cliqueNum_pairBlock n 2 3 := by  intro y hy  rw [b4_cliqueNum_mem_pairBlock_iff]  have hy0 := h_no_0 y hy  have hy1 := h_no_1 y hy  omegalemma b4_cliqueNum_card_le_of_isClique (n : Fin 4 → ℕ) (s : Finset (Σ i : Fin 4, Fin (n i)))    (hc : (b4_graph n).IsClique (s : Set (Σ i : Fin 4, Fin (n i)))) :    s.card ≤ max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by  by_cases h0 : ∃ x ∈ s, (x : Σ i : Fin 4, Fin (n i)).1 = 0  · rcases h0 with ⟨x, hx, hx0⟩    have hsub := b4_cliqueNum_case_0 n s hc x hx hx0    have hle := card_le_card hsub    rw [b4_cliqueNum_card_pairBlock n 0 1 (by decide)] at hle    exact le_trans hle (le_max_of_le_left (le_max_left _ _))  · push Not at h0    by_cases h1 : ∃ x ∈ s, (x : Σ i : Fin 4, Fin (n i)).1 = 1    · rcases h1 with ⟨x, hx, hx1⟩      have hsub := b4_cliqueNum_case_1 n s hc h0 x hx hx1      have hle := card_le_card hsub      rw [b4_cliqueNum_card_pairBlock n 1 3 (by decide)] at hle      exact le_trans hle (le_max_of_le_left (le_max_right _ _))    · push Not at h1      have hsub := b4_cliqueNum_case_23 n s h0 h1      have hle := card_le_card hsub      rw [b4_cliqueNum_card_pairBlock n 2 3 (by decide)] at hle      exact le_trans hle (le_max_right _ _)/-- The clique number of B_4(n_0, n_1, n_2, n_3) is max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3). -/theorem b4_cliqueNum (n : Fin 4 → ℕ) :    (b4_graph n).cliqueNum = max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by  apply le_antisymm  · obtain ⟨s, hs⟩ := (b4_graph n).exists_isNClique_cliqueNum    rw [isNClique_iff] at hs    rw [← hs.2]    exact b4_cliqueNum_card_le_of_isClique n s hs.1  · have h01 : n 0 + n 1 ≤ (b4_graph n).cliqueNum := by      have := (b4_cliqueNum_isClique_01 n).card_le_cliqueNum      rwa [b4_cliqueNum_card_pairBlock n 0 1 (by decide)] at this    have h13 : n 1 + n 3 ≤ (b4_graph n).cliqueNum := by      have := (b4_cliqueNum_isClique_13 n).card_le_cliqueNum      rwa [b4_cliqueNum_card_pairBlock n 1 3 (by decide)] at this    have h23 : n 2 + n 3 ≤ (b4_graph n).cliqueNum := by      have := (b4_cliqueNum_isClique_23 n).card_le_cliqueNum      rwa [b4_cliqueNum_card_pairBlock n 2 3 (by decide)] at this    exact max_le (max_le h01 h13) h23
See it in the graphDiscuss this resultChallenge it