in715_deficit_cover
Finite certificate for the explicit fourteen-vertex graph.
Statement
theorem in715_deficit_cover : ∀ t : Finset (Fin 14), G.IsNClique 3 t → ∃ e ∈ C, e ∈ t.sym2- Source
- Finite graph and certificates from experiments 20940 and 20968; see state/campaigns/triangle_reductions/outside_induced_kernel_in701.md.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- in715_deficit_p_sizeFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_properFinite certificate for the explicit fourteen-vertex graph.
- Used by 3
- in715_deficit_preciseAn explicit fourteen-vertex graph has a maximum seven-triangle packing, a seven-edge triangle cover, an outside five-cycle link and a…
- in715_deficit_pack_eqFinite certificate for the explicit fourteen-vertex graph.
- simple_graph_deficit_two_example_two_edge_dropDeleting two specified base edges from the explicit 14-vertex local-count counterexample decreases its triangle-packing number from seven…
The proof, explained
The theorem asserts that every 3-clique (triangle) in the graph G contains at least one edge from the certificate set C. Assuming for contradiction that a triangle t = {a, b, c} has no edges in C, the lemma in715_deficit_proper implies that every pair of its vertices must receive distinct colors under the map color : Fin 14 → Bool. However, since Bool has only two elements, the pigeonhole principle ensures that at least two of the three vertices must share a color, producing an immediate contradiction.
Let t = {a, b, c} be a 3-clique with pairwise distinct vertices a, b, and c.
We introduce the 3-clique t and the hypothesis ht that t is an n-clique of size 3. Since |t| = 3, Finset.card_eq_three.mp decomposes t into three distinct vertices a, b, c such that t = {a, b, c}.
uses
Finset.card_eq_three.mpclassical intro t ht obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp ht.card_eq
Assume for contradiction that no edge of the triangle {a, b, c} belongs to C.
We proceed by contradiction (by_contra) and push the negation into the existential quantifier (push_neg), yielding the assumption that every edge in C is outside the symmetric square {a, b, c}.sym2.
by_contra hn push_neg at hn
The vertices a, b, and c are pairwise adjacent in G.
Because {a, b, c} is a clique and the vertices a, b, c are distinct, each of the three pairs is connected by an edge in G, establishing G.Adj a b, G.Adj a c, and G.Adj b c.
have habG : G.Adj a b := ht.isClique (by simp) (by simp) hab have hacG : G.Adj a c := ht.isClique (by simp) (by simp) hac have hbcG : G.Adj b c := ht.isClique (by simp) (by simp) hbc
None of the three edges s(a, b), s(a, c), or s(b, c) belong to C.
Each unordered pair of vertices from {a, b, c} belongs to {a, b, c}.sym2 by Finset.mem_sym2_iff. Consequently, our contradiction hypothesis implies that s(a, b) ∉ C, s(a, c) ∉ C, and s(b, c) ∉ C.
uses
Finset.mem_sym2_iffhave habC : s(a,b) ∉ C := by intro h; exact hn _ h (by simp [Finset.mem_sym2_iff]) have hacC : s(a,c) ∉ C := by intro h; exact hn _ h (by simp [Finset.mem_sym2_iff]) have hbcC : s(b,c) ∉ C := by intro h; exact hn _ h (by simp [Finset.mem_sym2_iff])
The three vertices must all receive distinct colors under color.
Applying the lemma in715_deficit_proper to each pair of adjacent vertices whose edge lies outside C shows that color a ≠ color b, color a ≠ color c, and color b ≠ color c.
uses
in715_deficit_properhave hab' := in715_deficit_proper a b habG habC have hac' := in715_deficit_proper a c hacG hacC have hbc' := in715_deficit_proper b c hbcG hbcC
A contradiction arises because a 2-coloring cannot assign pairwise distinct colors to three vertices.
The function color takes values in Bool, which has only two elements. Exhaustive case analysis on whether color a, color b, and color c are true or false produces eight branches; in every branch, two vertices share a color, contradicting one of the three inequalities.
cases hA : color a <;> cases hB : color b <;> cases hC : color c <;> simp_all
Finset.card_eq_three.mp- A finite set has cardinality 3 if and only if it consists of three pairwise distinct elements; its forward implication decomposes such a set into {x, y, z} with x ≠ y, x ≠ z, and y ≠ z.
Finset.mem_sym2_iff- An unordered pair belongs to the symmetric square of a finite set s if and only if both of its endpoints belong to s.
in715_deficit_proper- If two vertices u and v are adjacent in G and the edge between them is not in C, then color u ≠ color v.
- The pigeonhole principle that no three vertices can receive pairwise distinct colors under a 2-coloring (`color : Fin 14 → Bool`) is handled by exhaustive case analysis over all 8 boolean assignments rather than by an explicit counting lemma.
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.
open scoped Sym2set_option maxRecDepth 100000set_option maxHeartbeats 30000000open In701Deficit14theorem in715_deficit_cover : ∀ t : Finset (Fin 14), G.IsNClique 3 t → ∃ e ∈ C, e ∈ t.sym2 := by classical intro t ht obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp ht.card_eq by_contra hn push_neg at hn have habG : G.Adj a b := ht.isClique (by simp) (by simp) hab have hacG : G.Adj a c := ht.isClique (by simp) (by simp) hac have hbcG : G.Adj b c := ht.isClique (by simp) (by simp) hbc have habC : s(a,b) ∉ C := by intro h; exact hn _ h (by simp [Finset.mem_sym2_iff]) have hacC : s(a,c) ∉ C := by intro h; exact hn _ h (by simp [Finset.mem_sym2_iff]) have hbcC : s(b,c) ∉ C := by intro h; exact hn _ h (by simp [Finset.mem_sym2_iff]) have hab' := in715_deficit_proper a b habG habC have hac' := in715_deficit_proper a c hacG hacC have hbc' := in715_deficit_proper b c hbcG hbcC cases hA : color a <;> cases hB : color b <;> cases hC : color c <;> simp_all