AFTD Auto-Formalizing Theoretical Domains

in715_deficit_pack_eq

theoremverified

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

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

    lines 7–8

    uses IsGreatest.csSup_eq, in715_deficit_p_tri, in715_deficit_p_disj, in715_deficit_p_size

      unfold simple_graph_triangle_packing_number
      refine IsGreatest.csSup_eq ⟨⟨P,in715_deficit_p_tri,in715_deficit_p_disj,in715_deficit_p_size⟩,?_⟩
  2. 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.

    lines 9–12

    uses in701_packing_le_edge_cover, in715_deficit_c_edges, in715_deficit_cover, in715_deficit_c_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
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

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