in715_deficit_p_size
Finite certificate for the explicit fourteen-vertex graph.
Statement
theorem in715_deficit_p_size : In701Deficit14.P.card = 7- 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 1
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
- Used by 30
- in715_deficit_z_okFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_11Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_13Finite certificate for the explicit fourteen-vertex graph.
- 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_proper_row_0Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_6Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_outsideFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_p_triFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_9Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_3Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_properFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_link_is_cycleFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_4Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_missingFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_5Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_pack_eqFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_c_sizeFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_xlinkFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_8Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_10Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_coverFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_x_okFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_2Finite 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…
- in715_deficit_proper_row_7Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_12Finite certificate for the explicit fourteen-vertex graph.
- in715_deficit_c_edgesFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_private_tipFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_p_disjFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_proper_row_1Finite certificate for the explicit fourteen-vertex graph.
The proof, explained
The theorem asserts that the family of vertex subsets P defined for the 14-vertex graph has cardinality 7. Because P is an explicit finite set of finite sets with decidable equality, the statement is proved by direct computation using Lean's kernel decision procedure (`decide +kernel`). The file also sets up the underlying simple graph on Fin 14, verifying the symmetry of its adjacency relation via Sym2.eq_swap.
The edge membership condition for adjacency is symmetric: if s(u, v) ∈ E, then s(v, u) ∈ E.
Rewriting with the symmetry of unordered pairs (`Sym2.eq_swap`) transforms s(v, u) into s(u, v), which is immediately discharged by the first conjunct of the adjacency hypothesis h.
uses
Sym2.eq_swapsymm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩
The family of subsets P has cardinality 7. automation
The set P is explicitly defined by enumerating seven 3-element subsets of vertices in Fin 14. Lean's kernel decision procedure (`decide +kernel`) computes the cardinality directly by verifying pairwise distinctness of the elements.
theorem in715_deficit_p_size : In701Deficit14.P.card = 7 := by decide +kernel
Sym2.eq_swap- The unordered pair constructor is symmetric: s(a, b) = s(b, a).
- The evaluation of the cardinality of P is carried out entirely by kernel computation (`decide +kernel`), which expands the explicit finite set definition and checks that all seven listed subsets are distinct.
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 30000000namespace In701Deficit14def E : Finset (Sym2 (Fin 14)) := {s(0,1), s(0,4), s(0,5), s(0,6), s(0,7), s(0,8), s(0,9), s(0,10), s(0,11), s(0,12), s(1,2), s(1,5), s(1,6), s(1,7), s(1,8), s(1,9), s(1,10), s(1,11), s(1,13), s(2,3), s(2,5), s(2,6), s(2,7), s(2,8), s(2,9), s(2,10), s(3,4), s(3,5), s(3,6), s(3,7), s(3,8), s(3,10), s(4,5), s(4,6), s(4,7), s(4,8), s(4,9), s(4,10), s(9,11), s(11,12), s(11,13)}def G : SimpleGraph (Fin 14) where Adj u v := s(u,v) ∈ E ∧ u ≠ v symm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩ loopless := ⟨fun u h => h.2 rfl⟩instance : DecidableRel G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ∈ E ∧ _ ≠ _))def P : Finset (Finset (Fin 14)) := {{0,1,5}, {1,2,6}, {2,3,7}, {3,4,8}, {0,4,9}, {0,11,12}, {1,11,13}}def C : Finset (Sym2 (Fin 14)) := {s(0,1), s(1,2), s(2,3), s(3,4), s(0,4), s(0,11), s(1,11)}def Z : Finset (Finset (Fin 14)) := {{0,1,9}, {1,2,9}, {0,4,9}, {0,9,11}, {1,9,11}}def X : Finset (Finset (Fin 14)) := {{0,1,10}, {1,2,10}, {2,3,10}, {3,4,10}, {0,4,10}}def color (v : Fin 14) : Bool := decide (v ∈ ({0,1,2,3,4,11} : Finset (Fin 14)))end In701Deficit14theorem in715_deficit_p_size : In701Deficit14.P.card = 7 := by decide +kernel