AFTD Auto-Formalizing Theoretical Domains

in715_deficit_precise

theoremverified

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

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 ⟨...⟩.

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

    lines 23–28

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

      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⟩
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

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