in715_deficit_pack_eq
Finite certificate for the explicit fourteen-vertex graph.
Statement
theorem in715_deficit_pack_eq : simple_graph_triangle_packing_number G = 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 8
- in715_deficit_p_sizeFinite certificate for the explicit fourteen-vertex graph.
- in701_packing_le_edge_coverA triangle packing has at most as many triangles as an edge cover.
- in715_deficit_p_triFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_p_disjFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_c_sizeFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_c_edgesFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_coverFinite certificate for the explicit fourteen-vertex graph.
- 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 1
- 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…
The proof, explained
The triangle packing number of the explicit 14-vertex graph $G$ is shown to be 7 by establishing matching lower and upper bounds. The lower bound is certified by an explicit packing $P$ of 7 pairwise edge-disjoint triangles. The upper bound follows from weak duality with triangle edge covers: an explicit edge cover $C$ of size 7 covers all triangles in $G$, ensuring that no edge-disjoint triangle packing can have more than 7 triangles.
The triangle packing number of $G$ equals 7 provided that 7 is an upper bound on the cardinality of any edge-disjoint triangle packing.
By definition, the triangle packing number of $G$ is the supremum of the sizes of all collections of pairwise edge-disjoint triangles in $G$. By IsGreatest.csSup_eq, this supremum equals 7 if 7 is the greatest element of the set of packing sizes. The explicit certificate $P$ attains this size: every member of $P$ is a triangle in $G$ (in715_deficit_p_tri), any two members share at most one vertex (in715_deficit_p_disj), and $|P| = 7$ (in715_deficit_p_size). This witnesses that 7 is in the set, reducing the claim to showing that 7 is an upper bound.
uses
IsGreatest.csSup_eq,in715_deficit_p_tri,in715_deficit_p_disj,in715_deficit_p_sizeunfold simple_graph_triangle_packing_number refine IsGreatest.csSup_eq ⟨⟨P,in715_deficit_p_tri,in715_deficit_p_disj,in715_deficit_p_size⟩,?_⟩
Every pairwise edge-disjoint triangle packing in $G$ has size at most 7.
Consider any collection $Q$ of pairwise edge-disjoint triangles in $G$. By weak duality between triangle packing and triangle edge covering (in701_packing_le_edge_cover), the size of $Q$ cannot exceed the size of any edge cover of the triangles in $G$. The explicit edge set $C$ consists of edges in $G$ (in715_deficit_c_edges) and covers every triangle of $G$ (in715_deficit_cover). Since $|C| = 7$ (in715_deficit_c_size), we obtain $|Q| \le 7$, which completes the proof.
uses
in701_packing_le_edge_cover,in715_deficit_c_edges,in715_deficit_cover,in715_deficit_c_sizerintro k ⟨Q,hQ,hpair,rfl⟩ have h := in701_packing_le_edge_cover G C in715_deficit_c_edges in715_deficit_cover Q hQ hpair rw [in715_deficit_c_size] at h exact h
IsGreatest.csSup_eq- If $a$ is the greatest element of a set $s$ in a conditionally complete partial order, then the supremum of $s$ is $a$.
in715_deficit_p_tri- Every element of the family $P$ is a triangle (a 3-clique) in the graph $G$.
in715_deficit_p_disj- Any two distinct triangles in $P$ intersect in at most one vertex, making them pairwise edge-disjoint.
in715_deficit_p_size- The family $P$ contains exactly 7 triangles.
in701_packing_le_edge_cover- The cardinality of any collection of pairwise edge-disjoint triangles is bounded above by the cardinality of any edge cover of all triangles in $G$.
in715_deficit_c_edges- Every element of $C$ is an edge of the graph $G$.
in715_deficit_cover- Every triangle in $G$ contains at least one edge from the set $C$.
in715_deficit_c_size- The edge set $C$ contains exactly 7 edges.
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_pack_eq : simple_graph_triangle_packing_number G = 7 := by unfold simple_graph_triangle_packing_number refine IsGreatest.csSup_eq ⟨⟨P,in715_deficit_p_tri,in715_deficit_p_disj,in715_deficit_p_size⟩,?_⟩ rintro k ⟨Q,hQ,hpair,rfl⟩ have h := in701_packing_le_edge_cover G C in715_deficit_c_edges in715_deficit_cover Q hQ hpair rw [in715_deficit_c_size] at h exact h