AFTD Auto-Formalizing Theoretical Domains

binary_function_graph_clique_free_three

theoremverifiedformalization

If a simple graph G has chromatic number strictly greater than 6, then its binary function graph is triangle-free (3-clique free).

Statement

theorem binary_function_graph_clique_free_three {V : Type*} (G : SimpleGraph V) (h : G.chromaticNumber > 6) : (binary_function_graph G).CliqueFree 3
Formalizes
arXiv:2610.37920 Lemma 2.3
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • binary_function_graphThe binary function graph of a simple graph G is the graph with vertices V → Bool, where two distinct functions f and g are adjacent if…
  • colorable_of_exists_indep_coverIf the vertex set of a graph G can be covered by k independent sets, then G is k-colorable.

Read back from the Lean

For any type V and any simple graph G on V, if the chromatic number of G is strictly greater than 6 (G.chromaticNumber > 6), then the graph binary_function_graph G is 3-clique-free (contains no clique of cardinality 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 theorem is proved by contradiction: suppose the binary function graph contains a triangle {x, y, z}. By definition of adjacency in the binary function graph, the sets of vertices where any pair of these functions agree on a given boolean value form independent sets in G, yielding six independent sets in total. By the pigeonhole principle, any vertex v must receive the same boolean value from at least two of the three functions, so these six independent sets cover all vertices of G. Covering the graph with six independent sets implies that G is 6-colorable and hence has chromatic number at most 6, contradicting the hypothesis that the chromatic number of G exceeds 6.

  1. Assume for contradiction that the binary function graph contains a 3-clique t, which can be represented by three distinct binary functions x, y, z : V → Bool.

    To prove that the binary function graph is triangle-free, we assume for contradiction that there exists a 3-clique t. Unfolding the definition with SimpleGraph.isNClique_iff shows that t is a clique with cardinality 3. By Finset.card_eq_three.mp, any 3-element finite set consists of three pairwise distinct elements x, y, and z, so t = {x, y, z}.

    lines 3–7

    uses SimpleGraph.isNClique_iff, Finset.card_eq_three.mp

      classical
      intro t ht
      rw [SimpleGraph.isNClique_iff] at ht
      obtain ⟨hclique, hcard⟩ := ht
      obtain ⟨x, y, z, hxy, hxz, hyz, rfl⟩ := Finset.card_eq_three.mp hcard
  2. The functions x, y, and z are pairwise adjacent in the binary function graph.

    Because {x, y, z} is a clique, every pair of distinct vertices in it is adjacent. Applying the clique property to the distinct pairs yields adjacency for x and y, x and z, and y and z.

    lines 8–10

      have hxy_adj : (binary_function_graph G).Adj x y := hclique (x := x) (by simp) (y := y) (by simp) hxy
      have hxz_adj : (binary_function_graph G).Adj x z := hclique (x := x) (by simp) (y := z) (by simp) hxz
      have hyz_adj : (binary_function_graph G).Adj y z := hclique (x := y) (by simp) (y := z) (by simp) hyz
  3. Define a family S₀, …, S₅ of six vertex subsets of V based on where pairs from {x, y, z} take identical boolean values.

    For each of the three pairs of functions and each boolean value b ∈ {false, true}, we define the set of vertices where both functions evaluate to b: S₀ = {v | x(v) = false ∧ y(v) = false}, S₁ = {v | x(v) = true ∧ y(v) = true}, S₂ = {v | x(v) = false ∧ z(v) = false}, S₃ = {v | x(v) = true ∧ z(v) = true}, S₄ = {v | y(v) = false ∧ z(v) = false}, and S₅ = {v | y(v) = true ∧ z(v) = true}.

    lines 11–16

      let S : Fin 6 → Set V := ![{v | x v = false ∧ y v = false},
        {v | x v = true ∧ y v = true},
        {v | x v = false ∧ z v = false},
        {v | x v = true ∧ z v = true},
        {v | y v = false ∧ z v = false},
        {v | y v = true ∧ z v = true}]
  4. Each of the six sets Sᵢ is an independent set in G.

    By the definition of adjacency in the binary function graph, two functions f and g are adjacent only if for each boolean value b, the agreement set {v | f(v) = b ∧ g(v) = b} is independent in G. Since x, y, and z are pairwise adjacent, each of S₀ through S₅ is an independent set. We check each index i ∈ {0, …, 5} by case exhaustion.

    lines 17–25

      have hS_indep : ∀ i, G.IsIndepSet (S i) := by
        intro i
        fin_cases i
        · exact hxy_adj.2 false
        · exact hxy_adj.2 true
        · exact hxz_adj.2 false
        · exact hxz_adj.2 true
        · exact hyz_adj.2 false
        · exact hyz_adj.2 true
  5. The six independent sets S₀, …, S₅ cover all vertices of G.

    For any vertex v ∈ V, the functions x, y, and z evaluate to a triple (x(v), y(v), z(v)) ∈ {false, true}³. Since three values are assigned into two possible booleans, by the pigeonhole principle at least two functions must agree. The proof checks all 2³ = 8 possible truth value assignments, exhibiting in every case an index i such that v ∈ Sᵢ.

    lines 26–36

      have hS_cover : ∀ v : V, ∃ i, v ∈ S i := by
        intro v
        cases hx : x v <;> cases hy : y v <;> cases hz : z v
        · exact ⟨0, by simp [S, hx, hy]⟩
        · exact ⟨0, by simp [S, hx, hy]⟩
        · exact ⟨2, by simp [S, hx, hz]⟩
        · exact ⟨5, by simp [S, hy, hz]⟩
        · exact ⟨4, by simp [S, hy, hz]⟩
        · exact ⟨3, by simp [S, hx, hz]⟩
        · exact ⟨1, by simp [S, hx, hy]⟩
        · exact ⟨1, by simp [S, hx, hy]⟩
  6. The graph G is 6-colorable, which implies its chromatic number is at most 6, contradicting the assumption that its chromatic number is strictly greater than 6.

    Since V is covered by 6 independent sets, G is 6-colorable by colorable_of_exists_indep_cover. Consequently, the chromatic number of G is at most 6. This contradicts the hypothesis that G has chromatic number > 6, using not_le_of_gt to close the proof.

    lines 37–39

    uses colorable_of_exists_indep_cover, not_le_of_gt

      have hcol : G.Colorable 6 := colorable_of_exists_indep_cover G S hS_indep hS_cover
      have hle : G.chromaticNumber ≤ (6 : ℕ∞) := hcol.chromaticNumber_le
      exact (not_le_of_gt h) hle
SimpleGraph.isNClique_iff
A finite set s is an n-clique in a graph if and only if s is a clique and has cardinality n.
Finset.card_eq_three.mp
A finite set has cardinality 3 if and only if it consists of three distinct elements x, y, z.
colorable_of_exists_indep_cover
If the vertices of a graph G can be covered by k independent sets, then G is k-colorable.
not_le_of_gt
In a preorder, if a < b then b ≤ a is false.

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

/-- If G has chromatic number > 6, then its binary function graph is triangle-free. -/theorem binary_function_graph_clique_free_three {V : Type*} (G : SimpleGraph V) (h : G.chromaticNumber > 6) : (binary_function_graph G).CliqueFree 3 := by  classical  intro t ht  rw [SimpleGraph.isNClique_iff] at ht  obtain ⟨hclique, hcard⟩ := ht  obtain ⟨x, y, z, hxy, hxz, hyz, rfl⟩ := Finset.card_eq_three.mp hcard  have hxy_adj : (binary_function_graph G).Adj x y := hclique (x := x) (by simp) (y := y) (by simp) hxy  have hxz_adj : (binary_function_graph G).Adj x z := hclique (x := x) (by simp) (y := z) (by simp) hxz  have hyz_adj : (binary_function_graph G).Adj y z := hclique (x := y) (by simp) (y := z) (by simp) hyz  let S : Fin 6 → Set V := ![{v | x v = false ∧ y v = false},    {v | x v = true ∧ y v = true},    {v | x v = false ∧ z v = false},    {v | x v = true ∧ z v = true},    {v | y v = false ∧ z v = false},    {v | y v = true ∧ z v = true}]  have hS_indep : ∀ i, G.IsIndepSet (S i) := by    intro i    fin_cases i    · exact hxy_adj.2 false    · exact hxy_adj.2 true    · exact hxz_adj.2 false    · exact hxz_adj.2 true    · exact hyz_adj.2 false    · exact hyz_adj.2 true  have hS_cover : ∀ v : V, ∃ i, v ∈ S i := by    intro v    cases hx : x v <;> cases hy : y v <;> cases hz : z v    · exact ⟨0, by simp [S, hx, hy]⟩    · exact ⟨0, by simp [S, hx, hy]⟩    · exact ⟨2, by simp [S, hx, hz]⟩    · exact ⟨5, by simp [S, hy, hz]⟩    · exact ⟨4, by simp [S, hy, hz]⟩    · exact ⟨3, by simp [S, hx, hz]⟩    · exact ⟨1, by simp [S, hx, hy]⟩    · exact ⟨1, by simp [S, hx, hy]⟩  have hcol : G.Colorable 6 := colorable_of_exists_indep_cover G S hS_indep hS_cover  have hle : G.chromaticNumber ≤ (6 : ℕ∞) := hcol.chromaticNumber_le  exact (not_le_of_gt h) hle
See it in the graphDiscuss this resultChallenge it