AFTD Auto-Formalizing Theoretical Domains

finite_packing_swap_no_valid_replacement_after_preprocessing

theoremverified

In the seven-vertex maximum-packing example, none of the three pairs of packed triangles admits a valid two-triangle replacement with greater vertex support, although the stated rule has a candidate that conflicts with the untouched third triangle. Every vertex and edge is triangle-active, each neighborhood is connected, and there is no four-clique.

Statement

theorem finite_packing_swap_no_valid_replacement_after_preprocessing :
  (∀ X Y : Finset (Fin 7), swapGraph604.IsNClique 3 X → swapGraph604.IsNClique 3 Y →
      ¬ swapImproves604 {0,1,2} {0,3,4} {1,3,5} X Y ∧
      ¬ swapImproves604 {0,1,2} {1,3,5} {0,3,4} X Y ∧
      ¬ swapImproves604 {0,3,4} {1,3,5} {0,1,2} X Y) ∧
  (∀ u v : Fin 7, swapGraph604.Adj u v → ∃ w : Fin 7, swapGraph604.Adj u w ∧ swapGraph604.Adj v w) ∧
  (∀ u : Fin 7, ∃ v : Fin 7, swapGraph604.Adj u v) ∧
  (∀ u v w : Fin 7, swapGraph604.Adj u v → swapGraph604.Adj u w →
      v = w ∨ swapGraph604.Adj v w ∨
      (∃ z : Fin 7, swapGraph604.Adj u z ∧ swapGraph604.Adj v z ∧ swapGraph604.Adj z w) ∨
      (∃ z z' : Fin 7, swapGraph604.Adj u z ∧ swapGraph604.Adj u z' ∧
        swapGraph604.Adj v z ∧ swapGraph604.Adj z z' ∧ swapGraph604.Adj z' w)) ∧
  (∀ t : Finset (Fin 7), ¬ swapGraph604.IsNClique 4 t)
Source
The replacement condition in Reduction Rule 8 of https://arxiv.org/html/2308.16515, Section 4.2, and its conference version; no claim is made about the kernel theorem or the later journal version.
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The theorem verifies that a maximum triangle packing on a 7-vertex graph admits no improving two-triangle swap, while satisfying several graph-theoretic preprocessing conditions: all vertices and edges are active in triangles, neighborhoods are connected, and there are no 4-cliques. The proof proceeds by exhaustively enumerating all six triangles in the graph, checking by finite evaluation that no pair of triangles can replace any of the three packed pairs with greater vertex support without violating edge-disjointness, and verifying the preprocessing conditions by decision procedures. Finally, these components are combined into the main conjunction.

  1. Every triangle in the graph is one of the six listed in swapAllTriangles604. automation

    By exhaustive evaluation on the finite graph of 7 vertices, every triple of mutually adjacent vertices forms a set belonging to the six-element collection swapAllTriangles604.

    lines 16–20

    theorem swap_triangle_table604 : ∀ a b c : Fin 7,
        swapGraph604.Adj a b → swapGraph604.Adj a c → swapGraph604.Adj b c →
          ({a,b,c} : Finset (Fin 7)) ∈ swapAllTriangles604 := by
      decide
    
  2. Every 3-clique in the graph belongs to swapAllTriangles604.

    A 3-clique t has cardinality 3, so it can be written as {a, b, c} with distinct vertices a, b, c. Because t is a clique, these vertices are pairwise adjacent, and applying swap_triangle_table604 shows {a, b, c} is in swapAllTriangles604.

    lines 21–28

    uses Finset.card_eq_three.mp, swap_triangle_table604

    theorem swap_triangle_list604 (t : Finset (Fin 7)) (ht : swapGraph604.IsNClique 3 t) :
        t ∈ swapAllTriangles604 := by
      obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp ht.card_eq
      exact swap_triangle_table604 a b c
        (ht.isClique (by simp) (by simp) hab)
        (ht.isClique (by simp) (by simp) hac)
        (ht.isClique (by simp) (by simp) hbc)
    
  3. No pair of triangles from swapAllTriangles604 gives an improving swap for any pair of packed triangles. automation

    By exhaustive evaluation across all 36 pairs of triangles in swapAllTriangles604, the decider checks that none improves the vertex coverage of any of the three pairs of packed triangles while remaining edge-disjoint from the third triangle.

    lines 29–35

    theorem swap_no_valid_replacement_table604 :
        ∀ X ∈ swapAllTriangles604, ∀ Y ∈ swapAllTriangles604,
          ¬ swapImproves604 {0,1,2} {0,3,4} {1,3,5} X Y ∧
          ¬ swapImproves604 {0,1,2} {1,3,5} {0,3,4} X Y ∧
          ¬ swapImproves604 {0,3,4} {1,3,5} {0,1,2} X Y := by
      decide
    
  4. No two 3-cliques in the graph admit an improving swap for any of the three pairs of packed triangles.

    Since every 3-clique belongs to swapAllTriangles604 by swap_triangle_list604, the result follows immediately from the exhaustive table check swap_no_valid_replacement_table604.

    lines 36–42

    uses swap_no_valid_replacement_table604, swap_triangle_list604

    theorem swap_no_valid_replacement604 (X Y : Finset (Fin 7))
        (hX : swapGraph604.IsNClique 3 X) (hY : swapGraph604.IsNClique 3 Y) :
          ¬ swapImproves604 {0,1,2} {0,3,4} {1,3,5} X Y ∧
          ¬ swapImproves604 {0,1,2} {1,3,5} {0,3,4} X Y ∧
          ¬ swapImproves604 {0,3,4} {1,3,5} {0,1,2} X Y :=
      swap_no_valid_replacement_table604 X (swap_triangle_list604 X hX) Y (swap_triangle_list604 Y hY)
    
  5. Every edge in the graph is triangle-active. automation

    By exhaustive verification, for every adjacent pair of vertices u and v, there exists a common neighbor w.

    lines 43–46

    theorem swap_all_edges_active604 : ∀ u v : Fin 7,
        swapGraph604.Adj u v → ∃ w : Fin 7, swapGraph604.Adj u w ∧ swapGraph604.Adj v w := by
      decide
    
  6. Every vertex in the graph is active. automation

    By exhaustive verification, every vertex u has at least one incident edge.

    lines 47–49

    theorem swap_all_vertices_active604 : ∀ u : Fin 7, ∃ v : Fin 7, swapGraph604.Adj u v := by
      decide
    
  7. Every vertex neighborhood in the graph is connected with diameter at most 3. automation

    By exhaustive verification, for any vertex u and any two of its neighbors v and w, either v = w, or v and w are adjacent, or they are connected by a path of length 2 or 3 through other neighbors of u.

    lines 50–57

    theorem swap_neighborhood_diameter_three604 : ∀ u v w : Fin 7,
        swapGraph604.Adj u v → swapGraph604.Adj u w →
          v = w ∨ swapGraph604.Adj v w ∨
          (∃ z : Fin 7, swapGraph604.Adj u z ∧ swapGraph604.Adj v z ∧ swapGraph604.Adj z w) ∨
          (∃ z z' : Fin 7, swapGraph604.Adj u z ∧ swapGraph604.Adj u z' ∧
            swapGraph604.Adj v z ∧ swapGraph604.Adj z z' ∧ swapGraph604.Adj z' w) := by
      decide
    
  8. The graph contains no 4-clique. automation

    By exhaustive verification over all 4-element subsets of vertices, no subset forms a 4-clique.

    lines 58–60

    theorem swap_no_four_clique604 : ∀ t : Finset (Fin 7), ¬ swapGraph604.IsNClique 4 t := by
      decide
    
  9. The five preprocessed packing and structural properties hold simultaneously.

    Assemble the five established properties into a conjunction.

    lines 61–75

    uses swap_no_valid_replacement604, swap_all_edges_active604, swap_all_vertices_active604, swap_neighborhood_diameter_three604, swap_no_four_clique604

    theorem finite_packing_swap_no_valid_replacement_after_preprocessing :
      (∀ X Y : Finset (Fin 7), swapGraph604.IsNClique 3 X → swapGraph604.IsNClique 3 Y →
          ¬ swapImproves604 {0,1,2} {0,3,4} {1,3,5} X Y ∧
          ¬ swapImproves604 {0,1,2} {1,3,5} {0,3,4} X Y ∧
          ¬ swapImproves604 {0,3,4} {1,3,5} {0,1,2} X Y) ∧
      (∀ u v : Fin 7, swapGraph604.Adj u v → ∃ w : Fin 7, swapGraph604.Adj u w ∧ swapGraph604.Adj v w) ∧
      (∀ u : Fin 7, ∃ v : Fin 7, swapGraph604.Adj u v) ∧
      (∀ u v w : Fin 7, swapGraph604.Adj u v → swapGraph604.Adj u w →
          v = w ∨ swapGraph604.Adj v w ∨
          (∃ z : Fin 7, swapGraph604.Adj u z ∧ swapGraph604.Adj v z ∧ swapGraph604.Adj z w) ∨
          (∃ z z' : Fin 7, swapGraph604.Adj u z ∧ swapGraph604.Adj u z' ∧
            swapGraph604.Adj v z ∧ swapGraph604.Adj z z' ∧ swapGraph604.Adj z' w)) ∧
      (∀ t : Finset (Fin 7), ¬ swapGraph604.IsNClique 4 t) := by
      exact ⟨swap_no_valid_replacement604, swap_all_edges_active604,
        swap_all_vertices_active604, swap_neighborhood_diameter_three604, swap_no_four_clique604⟩
Finset.card_eq_three.mp
A finite set of cardinality 3 can be expressed as a three-element set {x, y, z} of distinct elements.
swap_triangle_table604
Every triangle formed by three mutually adjacent vertices in the graph is in the list of six triangles.
swap_no_valid_replacement_table604
No pair of triangles from the explicit triangle list can replace any pair among the three packed triangles to increase vertex coverage without conflicting with the third triangle.
swap_triangle_list604
Every triangle (3-clique) in the graph belongs to the explicit list of six triangles.
swap_no_valid_replacement604
No two 3-cliques can validly replace any pair of packed triangles with greater vertex support.
swap_all_edges_active604
Every edge in the graph belongs to at least one triangle.
swap_all_vertices_active604
Every vertex in the graph has at least one incident edge.
swap_neighborhood_diameter_three604
For every vertex, any two of its neighbors are connected in its neighborhood by a path of length at most 3.
swap_no_four_clique604
The graph contains no 4-clique.

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

set_option maxRecDepth 100000set_option maxHeartbeats 8000000def swapAllTriangles604 : Finset (Finset (Fin 7)) :=  {{0,1,2}, {0,1,3}, {0,2,4}, {0,3,4}, {1,3,5}, {1,3,6}}def swapImproves604 (A B C X Y : Finset (Fin 7)) : Prop :=  X ⊆ (Finset.univ \ (A ∪ B ∪ C)) ∪ A ∪ B ∧  Y ⊆ (Finset.univ \ (A ∪ B ∪ C)) ∪ A ∪ B ∧  (A ∪ B).card < (X ∪ Y).card ∧  (X ∩ Y).card ≤ 1 ∧ (X ∩ C).card ≤ 1 ∧ (Y ∩ C).card ≤ 1instance (A B C X Y : Finset (Fin 7)) : Decidable (swapImproves604 A B C X Y) :=  inferInstanceAs (Decidable (_ ∧ _))theorem swap_triangle_table604 : ∀ a b c : Fin 7,    swapGraph604.Adj a b → swapGraph604.Adj a c → swapGraph604.Adj b c →      ({a,b,c} : Finset (Fin 7)) ∈ swapAllTriangles604 := by  decidetheorem swap_triangle_list604 (t : Finset (Fin 7)) (ht : swapGraph604.IsNClique 3 t) :    t ∈ swapAllTriangles604 := by  obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp ht.card_eq  exact swap_triangle_table604 a b c    (ht.isClique (by simp) (by simp) hab)    (ht.isClique (by simp) (by simp) hac)    (ht.isClique (by simp) (by simp) hbc)theorem swap_no_valid_replacement_table604 :    ∀ X ∈ swapAllTriangles604, ∀ Y ∈ swapAllTriangles604,      ¬ swapImproves604 {0,1,2} {0,3,4} {1,3,5} X Y ∧      ¬ swapImproves604 {0,1,2} {1,3,5} {0,3,4} X Y ∧      ¬ swapImproves604 {0,3,4} {1,3,5} {0,1,2} X Y := by  decidetheorem swap_no_valid_replacement604 (X Y : Finset (Fin 7))    (hX : swapGraph604.IsNClique 3 X) (hY : swapGraph604.IsNClique 3 Y) :      ¬ swapImproves604 {0,1,2} {0,3,4} {1,3,5} X Y ∧      ¬ swapImproves604 {0,1,2} {1,3,5} {0,3,4} X Y ∧      ¬ swapImproves604 {0,3,4} {1,3,5} {0,1,2} X Y :=  swap_no_valid_replacement_table604 X (swap_triangle_list604 X hX) Y (swap_triangle_list604 Y hY)theorem swap_all_edges_active604 : ∀ u v : Fin 7,    swapGraph604.Adj u v → ∃ w : Fin 7, swapGraph604.Adj u w ∧ swapGraph604.Adj v w := by  decidetheorem swap_all_vertices_active604 : ∀ u : Fin 7, ∃ v : Fin 7, swapGraph604.Adj u v := by  decidetheorem swap_neighborhood_diameter_three604 : ∀ u v w : Fin 7,    swapGraph604.Adj u v → swapGraph604.Adj u w →      v = w ∨ swapGraph604.Adj v w ∨      (∃ z : Fin 7, swapGraph604.Adj u z ∧ swapGraph604.Adj v z ∧ swapGraph604.Adj z w) ∨      (∃ z z' : Fin 7, swapGraph604.Adj u z ∧ swapGraph604.Adj u z' ∧        swapGraph604.Adj v z ∧ swapGraph604.Adj z z' ∧ swapGraph604.Adj z' w) := by  decidetheorem swap_no_four_clique604 : ∀ t : Finset (Fin 7), ¬ swapGraph604.IsNClique 4 t := by  decidetheorem finite_packing_swap_no_valid_replacement_after_preprocessing :  (∀ X Y : Finset (Fin 7), swapGraph604.IsNClique 3 X → swapGraph604.IsNClique 3 Y →      ¬ swapImproves604 {0,1,2} {0,3,4} {1,3,5} X Y ∧      ¬ swapImproves604 {0,1,2} {1,3,5} {0,3,4} X Y ∧      ¬ swapImproves604 {0,3,4} {1,3,5} {0,1,2} X Y) ∧  (∀ u v : Fin 7, swapGraph604.Adj u v → ∃ w : Fin 7, swapGraph604.Adj u w ∧ swapGraph604.Adj v w) ∧  (∀ u : Fin 7, ∃ v : Fin 7, swapGraph604.Adj u v) ∧  (∀ u v w : Fin 7, swapGraph604.Adj u v → swapGraph604.Adj u w →      v = w ∨ swapGraph604.Adj v w ∨      (∃ z : Fin 7, swapGraph604.Adj u z ∧ swapGraph604.Adj v z ∧ swapGraph604.Adj z w) ∨      (∃ z z' : Fin 7, swapGraph604.Adj u z ∧ swapGraph604.Adj u z' ∧        swapGraph604.Adj v z ∧ swapGraph604.Adj z z' ∧ swapGraph604.Adj z' w)) ∧  (∀ t : Finset (Fin 7), ¬ swapGraph604.IsNClique 4 t) := by  exact ⟨swap_no_valid_replacement604, swap_all_edges_active604,    swap_all_vertices_active604, swap_neighborhood_diameter_three604, swap_no_four_clique604⟩
See it in the graphDiscuss this resultChallenge it