binary_function_graph_clique_free_three
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.
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}.
uses
SimpleGraph.isNClique_iff,Finset.card_eq_three.mpclassical 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
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.
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
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}.
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}]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.
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
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ᵢ.
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]⟩
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.
uses
colorable_of_exists_indep_cover,not_le_of_gthave 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.
- The pigeonhole principle argument showing that the six sets cover all vertices of G is proved formally by exhaustive case analysis over the 8 possible truth value assignments for (x(v), y(v), z(v)) in {false, true}³.
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.
/-- 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