AFTD Auto-Formalizing Theoretical Domains

simple_graph_maximum_packing_fixed_two_budget_counterexample

theoremverified

A nine-vertex graph has a maximum triangle packing with at most one singleton-forced edge per packed triangle, but no triangle cover formed by choosing exactly two edges from each packed triangle. It nevertheless has a six-edge cover supported by that packing.

Statement

theorem simple_graph_maximum_packing_fixed_two_budget_counterexample :
    (∀ t ∈ In701Budget.P, In701Budget.G.IsNClique 3 t) ∧
    (In701Budget.P : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧
    In701Budget.P.card = simple_graph_triangle_packing_number In701Budget.G ∧
    (∀ p ∈ In701Budget.P, (finite_vertex_set_edge_encoding p ∩
      (((simple_graph_triangle_edge_family In701Budget.G).filter
        (fun t => (t ∩ In701Budget.P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1) ∧
    (∀ i : Fin 4, In701Budget.PI i ∈ In701Budget.P) ∧ Function.Injective In701Budget.PI ∧
    (∀ i : Fin 4, ∀ j : Fin 3, (In701Budget.Choice i j).card = 2 ∧ In701Budget.Choice i j ⊆ finite_vertex_set_edge_encoding (In701Budget.PI i)) ∧
    (∀ i : Fin 4, Function.Injective (In701Budget.Choice i)) ∧
    (∀ f : Fin 4 → Fin 3, ∃ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t ∧
      Disjoint (finite_vertex_set_edge_encoding t) (In701Budget.Picks f)) ∧
    (In701Budget.SmallCover.card = 6 ∧ In701Budget.SmallCover ⊆ In701Budget.P.biUnion finite_vertex_set_edge_encoding ∧
      ∀ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t → ¬ Disjoint (finite_vertex_set_edge_encoding t) In701Budget.SmallCover)
Source
Three four-cliques in a vertex cycle, extracted in experiments 20948 and 20962; see state/campaigns/triangle_reductions/k4_pivot_cover_in701.md. Related forced-triangle and packing-cover structure is in https://arxiv.org/abs/2001.00257, Section 3. Literature checked 2026-11-10.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The theorem constructs an explicit 9-vertex, 18-edge graph G showing that a maximum triangle packing P of size ν(G) = 4 cannot always yield a triangle cover by picking two edges from each packed triangle, even when each packed triangle has at most one singleton-forced edge. Exhaustive kernel evaluation (decide +kernel) characterizes the 13 triangles of G, establishes ν(G) = 4 via a compatibility search, and shows that all 3⁴ = 81 selections of two edges per packed triangle leave some triangle uncovered. Finally, an explicit 6-edge triangle cover supported entirely on the edges of P is verified to intersect every triangle in G.

  1. The graph G on 9 vertices is a well-defined simple graph with symmetric adjacency.

    The graph G is defined with vertices {0, ..., 8} and edges from the 18-element list EL. Adjacency requires s(u, v) ∈ E and u ≠ v. Symmetry is proved by swapping the unordered pair (Sym2.eq_swap), and looplessness is immediate from u ≠ v.

    lines 9–13

    uses Sym2.eq_swap

    def G : SimpleGraph (Fin 9) 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 ∧ _ ≠ _))
  2. The 3-cliques of G are precisely the 13 triples in T. automation

    The kernel checks by exhaustive evaluation (decide +kernel) that every 3-clique in G is listed in T (tri_complete) and that every element of T is a 3-clique (T_clique). Lemma clique_mem packages that any 3-clique of G belongs to T.

    lines 20–24

    theorem tri_complete : ∀ t ∈ (Finset.univ : Finset (Fin 9)).powersetCard 3,
        G.IsNClique 3 t → t ∈ T := by decide +kernel
    theorem T_clique : ∀ t ∈ T, G.IsNClique 3 t := by decide +kernel
    lemma clique_mem {t : Finset (Fin 9)} (h : G.IsNClique 3 t) : t ∈ T :=
      tri_complete t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _, h.card_eq⟩) h
  3. Every edge-disjoint triangle packing in G has size at most 4. automation

    Two triangles are edge-disjoint if and only if they share at most one vertex (compat). The kernel evaluates the compatibility search in693_maxC on T, finding maximum size 4 (maxC_eq). By in693_maxC_bound, any edge-disjoint triangle packing in G has size at most 4 (nu_le).

    lines 25–33

    uses in693_maxC_bound, maxC_eq

    def compat (s t : Finset (Fin 9)) : Bool := decide ((s ∩ t).card ≤ 1)
    theorem maxC_eq : in693_maxC compat T.length T = 4 := by decide +kernel
    lemma nu_le (U : Finset (Finset (Fin 9))) (hU : ∀ t ∈ U, G.IsNClique 3 t)
        (hP : (U : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : U.card ≤ 4 :=
      calc U.card ≤ in693_maxC compat T.length T :=
            in693_maxC_bound compat _ T le_rfl U (fun a ha => clique_mem (hU a ha))
              (fun a ha b hb hab => decide_eq_true (hP (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hb) hab))
        _ = 4 := maxC_eq
    
  4. P is an edge-disjoint triangle packing of size 4. automation

    The kernel verifies (decide +kernel) that the 4 triples in P are 3-cliques (P_clique), pairwise share at most one vertex (P_pw), and that |P| = 4 (P_card).

    lines 34–36

    theorem P_clique : ∀ t ∈ P, G.IsNClique 3 t := by decide +kernel
    theorem P_pw : (P : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kernel
    theorem P_card : P.card = 4 := by decide +kernel
  5. The maximum triangle packing number of G is 4.

    The packing number is defined as the supremum of sizes of edge-disjoint triangle packings. Since P achieves size 4 and every packing has size at most 4 by nu_le, 4 is the maximum of the set of packing sizes, hence equals its supremum via IsGreatest.csSup_eq.

    lines 37–42

    uses IsGreatest.csSup_eq, P_clique, P_pw, P_card, nu_le

    theorem pack_eq : simple_graph_triangle_packing_number G = 4 := by
      unfold simple_graph_triangle_packing_number
      refine IsGreatest.csSup_eq ⟨⟨P, P_clique, P_pw, P_card⟩, ?_⟩
      rintro n ⟨U, h1, h2, rfl⟩
      exact nu_le U h1 h2
    
  6. The triangle edge family of G equals the edge encodings of the triangles in T.

    By set extensionality and unfolding simple_graph_triangle_edge_family, an edge triple belongs to the family if and only if it encodes a 3-clique in G. This matches the edge encodings of T because all 3-cliques belong to T (clique_mem) and every element of T is a 3-clique (T_clique).

    lines 43–51

    uses clique_mem, T_clique

    theorem family : simple_graph_triangle_edge_family G =
        T.toFinset.image finite_vertex_set_edge_encoding := by
      classical
      ext x
      simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, List.mem_toFinset]
      constructor
      · rintro ⟨t, ht, rfl⟩; exact ⟨t, clique_mem ht, rfl⟩
      · rintro ⟨t, ht, rfl⟩; exact ⟨t, T_clique t ht, rfl⟩
    
  7. Each packed triangle in P contains at most one singleton-forced edge. automation

    Rewriting with family expresses the triangle edge family in terms of T. The kernel then verifies (decide +kernel) that for each p ∈ P, at most one edge belongs to triangles that share only that single edge with the packing P.

    lines 52–57

    uses family

    theorem forced_le : ∀ p ∈ P, (finite_vertex_set_edge_encoding p ∩
       (((simple_graph_triangle_edge_family G).filter
         (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1 := by
      rw [family]
      decide +kernel
    
  8. The indexing and choices of two edges per packed triangle are well-defined. automation

    The kernel verifies (decide +kernel) that PI indexes the 4 triangles of P injectively, and that Choice specifies 3 distinct pairs of edges from each packed triangle.

    lines 58–60

    theorem choices_ok : (∀ i : Fin 4, PI i ∈ P) ∧ Function.Injective PI ∧
        (∀ i : Fin 4, ∀ j : Fin 3, (Choice i j).card = 2 ∧ Choice i j ⊆ finite_vertex_set_edge_encoding (PI i)) ∧
        (∀ i : Fin 4, Function.Injective (Choice i)) := by decide +kernel
  9. No selection of two edges per packed triangle forms a triangle cover. automation

    The kernel checks all 3⁴ = 81 selection functions f (decide +kernel), finding for each selection some triangle t ∈ T whose edges are completely disjoint from the chosen edges Picks f.

    lines 61–63

    theorem no_selection : ∀ f : Fin 4 → Fin 3, ∃ t ∈ T,
        Disjoint (finite_vertex_set_edge_encoding t) (Picks f) := by decide +kernel
  10. SmallCover is a 6-edge triangle cover supported entirely on P. automation

    The kernel verifies (decide +kernel) that SmallCover has size 6, uses only edges of P, and intersects every triangle in T.

    lines 64–67

    theorem small_cover : SmallCover.card = 6 ∧ SmallCover ⊆ P.biUnion finite_vertex_set_edge_encoding ∧
        ∀ t ∈ T, ¬ Disjoint (finite_vertex_set_edge_encoding t) SmallCover := by decide +kernel
    end In701Budget
  11. P is a maximum packing with at most one singleton-forced edge per triangle, and |P| = ν(G).

    The main theorem decomposes into conjuncts. P_clique, P_pw, forced_le, and choices_ok provide the packing properties, singleton-forced edge bound, and choice validity. Rewriting with P_card and pack_eq shows |P| = ν(G) = 4.

    lines 69–84

    uses In701Budget.P_clique, In701Budget.P_pw, In701Budget.forced_le, In701Budget.choices_ok, In701Budget.P_card, In701Budget.pack_eq

    theorem simple_graph_maximum_packing_fixed_two_budget_counterexample :
        (∀ t ∈ In701Budget.P, In701Budget.G.IsNClique 3 t) ∧
        (In701Budget.P : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧
        In701Budget.P.card = simple_graph_triangle_packing_number In701Budget.G ∧
        (∀ p ∈ In701Budget.P, (finite_vertex_set_edge_encoding p ∩
          (((simple_graph_triangle_edge_family In701Budget.G).filter
            (fun t => (t ∩ In701Budget.P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1) ∧
        (∀ i : Fin 4, In701Budget.PI i ∈ In701Budget.P) ∧ Function.Injective In701Budget.PI ∧
        (∀ i : Fin 4, ∀ j : Fin 3, (In701Budget.Choice i j).card = 2 ∧ In701Budget.Choice i j ⊆ finite_vertex_set_edge_encoding (In701Budget.PI i)) ∧
        (∀ i : Fin 4, Function.Injective (In701Budget.Choice i)) ∧
        (∀ f : Fin 4 → Fin 3, ∃ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t ∧
          Disjoint (finite_vertex_set_edge_encoding t) (In701Budget.Picks f)) ∧
        (In701Budget.SmallCover.card = 6 ∧ In701Budget.SmallCover ⊆ In701Budget.P.biUnion finite_vertex_set_edge_encoding ∧
          ∀ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t → ¬ Disjoint (finite_vertex_set_edge_encoding t) In701Budget.SmallCover) := by
      refine ⟨In701Budget.P_clique,In701Budget.P_pw,?_,In701Budget.forced_le,In701Budget.choices_ok.1,In701Budget.choices_ok.2.1,In701Budget.choices_ok.2.2.1,In701Budget.choices_ok.2.2.2,?_,?_⟩
      · rw [In701Budget.P_card,In701Budget.pack_eq]
  12. Every selection of two edges per packed triangle leaves some triangle in G uncovered.

    Given a selection f, no_selection yields an uncovered triangle t ∈ T. Since t is a 3-clique in G by T_clique, this witnesses that the selection fails to cover all 3-cliques.

    lines 85–87

    uses In701Budget.no_selection, In701Budget.T_clique

      · intro f
        obtain ⟨t,ht,hd⟩ := In701Budget.no_selection f
        exact ⟨t,In701Budget.T_clique t ht,hd⟩
  13. SmallCover is a 6-edge triangle cover of G supported on P.

    The cardinality 6 and support on P follow from small_cover. Any 3-clique t of G belongs to T by clique_mem, so small_cover guarantees that SmallCover shares an edge with t.

    lines 88–90

    uses In701Budget.small_cover, In701Budget.clique_mem

      · refine ⟨In701Budget.small_cover.1,In701Budget.small_cover.2.1,?_⟩
        intro t ht
        exact In701Budget.small_cover.2.2 t (In701Budget.clique_mem ht)
Sym2.eq_swap
An unordered pair s(a, b) is equal to s(b, a).
clique_mem
Every 3-clique in G belongs to the list of triangles T.
family
The triangle edge family of G is the set of edge encodings of the triples in T.
in693_maxC_bound
If a list l has length at most n, any pairwise c-compatible sub-collection of l has size at most in693_maxC c n l.
IsGreatest.csSup_eq
If an element a is the greatest element of a set s, then sSup s = a.
maxC_eq
The compatibility search algorithm certifies that the maximum number of pairwise edge-disjoint triangles in T is 4.
nu_le
Any collection of pairwise edge-disjoint 3-cliques in G has cardinality at most 4.
P_card
The packing P has cardinality 4.
P_clique
Every triple in P spans a 3-clique in G.
P_pw
The triangles in P are pairwise edge-disjoint (sharing at most one vertex).
T_clique
Every element of T spans a 3-clique in G.
In701Budget.choices_ok
The choices of two edges per packed triangle are well-defined and distinct.
In701Budget.clique_mem
Any 3-clique of G belongs to T.
In701Budget.forced_le
Each triangle in P contains at most one singleton-forced edge.
In701Budget.no_selection
For any choice of two edges per packed triangle, some triangle in T remains uncovered.
In701Budget.P_card
The packing P contains 4 triangles.
In701Budget.P_clique
Every triple in P is a 3-clique in G.
In701Budget.P_pw
The triangles in P pairwise share at most one vertex.
In701Budget.pack_eq
The maximum triangle packing number of G is 4.
In701Budget.small_cover
SmallCover has size 6, uses only edges of P, and intersects every triangle in T.
In701Budget.T_clique
Every triple in T is a 3-clique in G.

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 30000000namespace In701Budgetdef EL : List (Sym2 (Fin 9)) := [s(0,1), s(0,2), s(0,3), s(1,2), s(1,3), s(2,3), s(2,5), s(2,7), s(2,8), s(3,4), s(3,5), s(3,6), s(4,5), s(4,6), s(5,6), s(5,7), s(5,8), s(7,8)]def T : List (Finset (Fin 9)) := [{0,1,2}, {0,1,3}, {0,2,3}, {1,2,3}, {2,3,5}, {2,5,7}, {2,5,8}, {2,7,8}, {3,4,5}, {3,4,6}, {3,5,6}, {4,5,6}, {5,7,8}]def P : Finset (Finset (Fin 9)) := {{0,1,2}, {3,4,6}, {2,3,5}, {2,7,8}}def E : Finset (Sym2 (Fin 9)) := EL.toFinsetdef G : SimpleGraph (Fin 9) 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 PI : Fin 4 → Finset (Fin 9) := ![{0,1,2}, {3,4,6}, {2,3,5}, {2,7,8}]def Choice : Fin 4 → Fin 3 → Finset (Sym2 (Fin 9)) := ![![{s(0,1), s(0,2)}, {s(0,1), s(1,2)}, {s(0,2), s(1,2)}], ![{s(3,4), s(3,6)}, {s(3,4), s(4,6)}, {s(3,6), s(4,6)}], ![{s(2,3), s(2,5)}, {s(2,3), s(3,5)}, {s(2,5), s(3,5)}], ![{s(2,7), s(2,8)}, {s(2,7), s(7,8)}, {s(2,8), s(7,8)}]]def SmallCover : Finset (Sym2 (Fin 9)) := {s(0,1), s(2,3), s(2,5), s(3,5), s(4,6), s(7,8)}def Picks (f : Fin 4 → Fin 3) : Finset (Sym2 (Fin 9)) :=  (Finset.univ : Finset (Fin 4)).biUnion (fun i => Choice i (f i))theorem tri_complete : ∀ t ∈ (Finset.univ : Finset (Fin 9)).powersetCard 3,    G.IsNClique 3 t → t ∈ T := by decide +kerneltheorem T_clique : ∀ t ∈ T, G.IsNClique 3 t := by decide +kernellemma clique_mem {t : Finset (Fin 9)} (h : G.IsNClique 3 t) : t ∈ T :=  tri_complete t (Finset.mem_powersetCard.mpr ⟨Finset.subset_univ _, h.card_eq⟩) hdef compat (s t : Finset (Fin 9)) : Bool := decide ((s ∩ t).card ≤ 1)theorem maxC_eq : in693_maxC compat T.length T = 4 := by decide +kernellemma nu_le (U : Finset (Finset (Fin 9))) (hU : ∀ t ∈ U, G.IsNClique 3 t)    (hP : (U : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1)) : U.card ≤ 4 :=  calc U.card ≤ in693_maxC compat T.length T :=        in693_maxC_bound compat _ T le_rfl U (fun a ha => clique_mem (hU a ha))          (fun a ha b hb hab => decide_eq_true (hP (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hb) hab))    _ = 4 := maxC_eqtheorem P_clique : ∀ t ∈ P, G.IsNClique 3 t := by decide +kerneltheorem P_pw : (P : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by decide +kerneltheorem P_card : P.card = 4 := by decide +kerneltheorem pack_eq : simple_graph_triangle_packing_number G = 4 := by  unfold simple_graph_triangle_packing_number  refine IsGreatest.csSup_eq ⟨⟨P, P_clique, P_pw, P_card⟩, ?_⟩  rintro n ⟨U, h1, h2, rfl⟩  exact nu_le U h1 h2theorem family : simple_graph_triangle_edge_family G =    T.toFinset.image finite_vertex_set_edge_encoding := by  classical  ext x  simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, List.mem_toFinset]  constructor  · rintro ⟨t, ht, rfl⟩; exact ⟨t, clique_mem ht, rfl⟩  · rintro ⟨t, ht, rfl⟩; exact ⟨t, T_clique t ht, rfl⟩theorem forced_le : ∀ p ∈ P, (finite_vertex_set_edge_encoding p ∩   (((simple_graph_triangle_edge_family G).filter     (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1 := by  rw [family]  decide +kerneltheorem choices_ok : (∀ i : Fin 4, PI i ∈ P) ∧ Function.Injective PI ∧    (∀ i : Fin 4, ∀ j : Fin 3, (Choice i j).card = 2 ∧ Choice i j ⊆ finite_vertex_set_edge_encoding (PI i)) ∧    (∀ i : Fin 4, Function.Injective (Choice i)) := by decide +kerneltheorem no_selection : ∀ f : Fin 4 → Fin 3, ∃ t ∈ T,    Disjoint (finite_vertex_set_edge_encoding t) (Picks f) := by decide +kerneltheorem small_cover : SmallCover.card = 6 ∧ SmallCover ⊆ P.biUnion finite_vertex_set_edge_encoding ∧    ∀ t ∈ T, ¬ Disjoint (finite_vertex_set_edge_encoding t) SmallCover := by decide +kernelend In701Budgettheorem simple_graph_maximum_packing_fixed_two_budget_counterexample :    (∀ t ∈ In701Budget.P, In701Budget.G.IsNClique 3 t) ∧    (In701Budget.P : Set (Finset (Fin 9))).Pairwise (fun a b => (a ∩ b).card ≤ 1) ∧    In701Budget.P.card = simple_graph_triangle_packing_number In701Budget.G ∧    (∀ p ∈ In701Budget.P, (finite_vertex_set_edge_encoding p ∩      (((simple_graph_triangle_edge_family In701Budget.G).filter        (fun t => (t ∩ In701Budget.P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card ≤ 1) ∧    (∀ i : Fin 4, In701Budget.PI i ∈ In701Budget.P) ∧ Function.Injective In701Budget.PI ∧    (∀ i : Fin 4, ∀ j : Fin 3, (In701Budget.Choice i j).card = 2 ∧ In701Budget.Choice i j ⊆ finite_vertex_set_edge_encoding (In701Budget.PI i)) ∧    (∀ i : Fin 4, Function.Injective (In701Budget.Choice i)) ∧    (∀ f : Fin 4 → Fin 3, ∃ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t ∧      Disjoint (finite_vertex_set_edge_encoding t) (In701Budget.Picks f)) ∧    (In701Budget.SmallCover.card = 6 ∧ In701Budget.SmallCover ⊆ In701Budget.P.biUnion finite_vertex_set_edge_encoding ∧      ∀ t : Finset (Fin 9), In701Budget.G.IsNClique 3 t → ¬ Disjoint (finite_vertex_set_edge_encoding t) In701Budget.SmallCover) := by  refine ⟨In701Budget.P_clique,In701Budget.P_pw,?_,In701Budget.forced_le,In701Budget.choices_ok.1,In701Budget.choices_ok.2.1,In701Budget.choices_ok.2.2.1,In701Budget.choices_ok.2.2.2,?_,?_⟩  · rw [In701Budget.P_card,In701Budget.pack_eq]  · intro f    obtain ⟨t,ht,hd⟩ := In701Budget.no_selection f    exact ⟨t,In701Budget.T_clique t ht,hd⟩  · refine ⟨In701Budget.small_cover.1,In701Budget.small_cover.2.1,?_⟩    intro t ht    exact In701Budget.small_cover.2.2 t (In701Budget.clique_mem ht)
See it in the graphDiscuss this resultChallenge it