in715_deficit_precise
An explicit fourteen-vertex graph has a maximum seven-triangle packing, a seven-edge triangle cover, an outside five-cycle link and a private packed tip missing a link vertex despite belonging to at least five triangles.
Statement
theorem in715_deficit_precise : (∀ e ∈ In701Deficit14.C, e ∈ In701Deficit14.G.edgeSet) ∧ In701Deficit14.C.card = 7 ∧ (∀ t : Finset (Fin 14), In701Deficit14.G.IsNClique 3 t → ∃ e ∈ In701Deficit14.C, e ∈ t.sym2) ∧ (∀ t ∈ In701Deficit14.P, In701Deficit14.G.IsNClique 3 t) ∧ (In701Deficit14.P : Set (Finset (Fin 14))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧ In701Deficit14.P.card = 7 ∧ simple_graph_triangle_packing_number In701Deficit14.G = 7 ∧ (10 : Fin 14) ∉ In701Deficit14.P.biUnion id ∧ ¬ In701Deficit14.G.Adj 9 3 ∧ ({0,4,9} : Finset (Fin 14)) ∈ In701Deficit14.P ∧ (∀ t ∈ In701Deficit14.P, (9 : Fin 14) ∈ t → t = ({0,4,9} : Finset (Fin 14))) ∧ (∀ v : Fin 14, In701Deficit14.G.Adj 10 v ↔ v ∈ ({0,1,2,3,4} : Finset (Fin 14))) ∧ (∀ u v : Fin 14, u ∈ ({0,1,2,3,4} : Finset (Fin 14)) → v ∈ ({0,1,2,3,4} : Finset (Fin 14)) → (In701Deficit14.G.Adj u v ↔ s(u,v) ∈ ({s(0,1),s(1,2),s(2,3),s(3,4),s(0,4)} : Finset (Sym2 (Fin 14))))) ∧ In701Deficit14.Z.card = 5 ∧ (∀ t ∈ In701Deficit14.Z, In701Deficit14.G.IsNClique 3 t ∧ (9 : Fin 14) ∈ t)
- 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 14
- in715_deficit_p_sizeFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_link_is_cycleFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_c_edgesFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_c_sizeFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_coverFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_p_triFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_p_disjFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_pack_eqFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_outsideFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_missingFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_private_tipFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_xlinkFinite certificate for the explicit fourteen-vertex graph.
- in715_deficit_z_okFinite 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
- 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 collects fifteen structural properties of an explicit 14-vertex graph G, establishing that its maximum edge-disjoint triangle packing number and minimum triangle cover size are both 7, with an uncovered vertex whose link is an induced 5-cycle, and a packed triangle possessing a private tip vertex that misses one of the link vertices while participating in at least 5 triangles. The proof simply assembles the fifteen individual lemmas proved earlier into a single conjunction using the constructor tuple ⟨...⟩.
The graph G and sets C, P, and Z satisfy all fifteen stated properties.
The theorem is a 15-way conjunction packaging the structural properties of G, C, P, and Z into a single record. The exact tactic closes the goal by supplying witnesses for all 15 conjuncts directly from previously proved lemmas: C is a 7-edge triangle cover (in715_deficit_c_edges, in715_deficit_c_size, in715_deficit_cover); P is an edge-disjoint 7-triangle packing attaining the maximum packing number (in715_deficit_p_tri, in715_deficit_p_disj, in715_deficit_p_size, in715_deficit_pack_eq); vertex 10 is outside P and vertex 9 is not adjacent to 3 (in715_deficit_outside, in715_deficit_missing); {0, 4, 9} is the unique triangle in P containing vertex 9 (in715_deficit_private_tip.1, in715_deficit_private_tip.2); the neighborhood of vertex 10 is an induced 5-cycle on {0, 1, 2, 3, 4} (in715_deficit_xlink, in715_deficit_link_is_cycle); and Z exhibits 5 triangles in G incident to vertex 9 (in715_deficit_z_ok.1, in715_deficit_z_ok.2).
uses
in715_deficit_c_edges,in715_deficit_c_size,in715_deficit_cover,in715_deficit_p_tri,in715_deficit_p_disj,in715_deficit_p_size,in715_deficit_pack_eq,in715_deficit_outside,in715_deficit_missing,in715_deficit_private_tip.1,in715_deficit_private_tip.2,in715_deficit_xlink,in715_deficit_link_is_cycle,in715_deficit_z_ok.1,in715_deficit_z_ok.2exact ⟨in715_deficit_c_edges, in715_deficit_c_size, in715_deficit_cover, in715_deficit_p_tri, in715_deficit_p_disj, in715_deficit_p_size, in715_deficit_pack_eq, in715_deficit_outside, in715_deficit_missing, in715_deficit_private_tip.1, in715_deficit_private_tip.2, in715_deficit_xlink, in715_deficit_link_is_cycle, in715_deficit_z_ok.1, in715_deficit_z_ok.2⟩
in715_deficit_c_edges- Every edge in C is an edge of the graph G.
in715_deficit_c_size- The set C contains exactly 7 edges.
in715_deficit_cover- Every triangle in G contains at least one edge in C, so C is a triangle cover.
in715_deficit_p_tri- Every member of P is a triangle (3-clique) in G.
in715_deficit_p_disj- Any two distinct triangles in P share at most one vertex, so P is an edge-disjoint triangle packing.
in715_deficit_p_size- The packing P contains exactly 7 triangles.
in715_deficit_pack_eq- The maximum size of an edge-disjoint triangle packing in G is 7.
in715_deficit_outside- Vertex 10 is outside the packing P (it does not belong to any triangle in P).
in715_deficit_missing- Vertex 9 is not adjacent to vertex 3 in G.
in715_deficit_private_tip.1- The triangle {0, 4, 9} belongs to the packing P.
in715_deficit_private_tip.2- The only triangle in P that contains vertex 9 is {0, 4, 9}.
in715_deficit_xlink- A vertex is adjacent to vertex 10 in G if and only if it belongs to {0, 1, 2, 3, 4}.
in715_deficit_link_is_cycle- The subgraph induced on {0, 1, 2, 3, 4} is a 5-cycle with edges {0,1}, {1,2}, {2,3}, {3,4}, and {0,4}.
in715_deficit_z_ok.1- The set Z contains exactly 5 triangles.
in715_deficit_z_ok.2- Every triangle in Z is a triangle of G containing vertex 9.
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 30000000theorem in715_deficit_precise : (∀ e ∈ In701Deficit14.C, e ∈ In701Deficit14.G.edgeSet) ∧ In701Deficit14.C.card = 7 ∧ (∀ t : Finset (Fin 14), In701Deficit14.G.IsNClique 3 t → ∃ e ∈ In701Deficit14.C, e ∈ t.sym2) ∧ (∀ t ∈ In701Deficit14.P, In701Deficit14.G.IsNClique 3 t) ∧ (In701Deficit14.P : Set (Finset (Fin 14))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧ In701Deficit14.P.card = 7 ∧ simple_graph_triangle_packing_number In701Deficit14.G = 7 ∧ (10 : Fin 14) ∉ In701Deficit14.P.biUnion id ∧ ¬ In701Deficit14.G.Adj 9 3 ∧ ({0,4,9} : Finset (Fin 14)) ∈ In701Deficit14.P ∧ (∀ t ∈ In701Deficit14.P, (9 : Fin 14) ∈ t → t = ({0,4,9} : Finset (Fin 14))) ∧ (∀ v : Fin 14, In701Deficit14.G.Adj 10 v ↔ v ∈ ({0,1,2,3,4} : Finset (Fin 14))) ∧ (∀ u v : Fin 14, u ∈ ({0,1,2,3,4} : Finset (Fin 14)) → v ∈ ({0,1,2,3,4} : Finset (Fin 14)) → (In701Deficit14.G.Adj u v ↔ s(u,v) ∈ ({s(0,1),s(1,2),s(2,3),s(3,4),s(0,4)} : Finset (Sym2 (Fin 14))))) ∧ In701Deficit14.Z.card = 5 ∧ (∀ t ∈ In701Deficit14.Z, In701Deficit14.G.IsNClique 3 t ∧ (9 : Fin 14) ∈ t) := by exact ⟨in715_deficit_c_edges, in715_deficit_c_size, in715_deficit_cover, in715_deficit_p_tri, in715_deficit_p_disj, in715_deficit_p_size, in715_deficit_pack_eq, in715_deficit_outside, in715_deficit_missing, in715_deficit_private_tip.1, in715_deficit_private_tip.2, in715_deficit_xlink, in715_deficit_link_is_cycle, in715_deficit_z_ok.1, in715_deficit_z_ok.2⟩