finite_packing_swap_no_valid_replacement_after_preprocessing
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
- finite_maximal_packing_two_triangle_swap_counterexampleA finite graph has a maximal packing of three edge-disjoint triangles A, B, C and two edge-disjoint triangles X, Y contained in the…
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.
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.
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
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.
uses
Finset.card_eq_three.mp,swap_triangle_table604theorem 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)
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.
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
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.
uses
swap_no_valid_replacement_table604,swap_triangle_list604theorem 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)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.
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
Every vertex in the graph is active. automation
By exhaustive verification, every vertex u has at least one incident edge.
theorem swap_all_vertices_active604 : ∀ u : Fin 7, ∃ v : Fin 7, swapGraph604.Adj u v := by decide
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.
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
The graph contains no 4-clique. automation
By exhaustive verification over all 4-element subsets of vertices, no subset forms a 4-clique.
theorem swap_no_four_clique604 : ∀ t : Finset (Fin 7), ¬ swapGraph604.IsNClique 4 t := by decide
The five preprocessed packing and structural properties hold simultaneously.
Assemble the five established properties into a conjunction.
uses
swap_no_valid_replacement604,swap_all_edges_active604,swap_all_vertices_active604,swap_neighborhood_diameter_three604,swap_no_four_clique604theorem 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
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.
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⟩