AFTD Auto-Formalizing Theoretical Domains

in715_deficit_cover

theoremverified

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
Used by 3

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.

  1. 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}.

    lines 7–9

    uses Finset.card_eq_three.mp

      classical
      intro t ht
      obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp ht.card_eq
  2. 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.

    lines 10–11

      by_contra hn
      push_neg at hn
  3. 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.

    lines 12–14

      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
  4. 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.

    lines 15–17

    uses Finset.mem_sym2_iff

      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])
  5. 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.

    lines 18–20

    uses in715_deficit_proper

      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
  6. 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.

    line 21

      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.

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 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
See it in the graphDiscuss this resultChallenge it