finite_maximal_packing_two_triangle_swap_counterexample
A finite graph has a maximal packing of three edge-disjoint triangles A, B, C and two edge-disjoint triangles X, Y contained in the vertices of A and B together with vertices outside the packing, such that X and Y cover more vertices than A and B but X shares an edge with C. The graph also has the displayed three-edge triangle cover.
Statement
theorem finite_maximal_packing_two_triangle_swap_counterexample :
∃ (G : SimpleGraph (Fin 7)) (A B C X Y : Finset (Fin 7)),
G.IsNClique 3 A ∧ G.IsNClique 3 B ∧ G.IsNClique 3 C ∧
(A ∩ B).card ≤ 1 ∧ (A ∩ C).card ≤ 1 ∧ (B ∩ C).card ≤ 1 ∧
G.IsNClique 3 X ∧ G.IsNClique 3 Y ∧ (X ∩ Y).card ≤ 1 ∧
X ⊆ (Finset.univ \ (A ∪ B ∪ C)) ∪ A ∪ B ∧
Y ⊆ (Finset.univ \ (A ∪ B ∪ C)) ∪ A ∪ B ∧
(A ∪ B).card < (X ∪ Y).card ∧ 2 ≤ (X ∩ C).card ∧
(∀ t : Finset (Fin 7), G.IsNClique 3 t →
2 ≤ (A ∩ t).card ∨ 2 ≤ (B ∩ t).card ∨ 2 ≤ (C ∩ t).card) ∧
(∀ a b c : Fin 7, G.Adj a b → G.Adj a c → G.Adj b c →
((0 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7)) ∧ (1 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7))) ∨
((0 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7)) ∧ (4 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7))) ∨
((1 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7)) ∧ (3 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7))))- Source
- Counterexample to the literal replacement in Reduction Rule 8 of https://arxiv.org/html/2308.16515, Section 4.2; this does not refute the paper’s kernel-size theorem.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- finite_packing_swap_no_valid_replacement_after_preprocessingIn the seven-vertex maximum-packing example, none of the three pairs of packed triangles admits a valid two-triangle replacement with…
The proof, explained
We construct an explicit 7-vertex graph swapGraph604 with 12 edges and five triangles: a packing of three edge-disjoint triangles A = {0, 1, 2}, B = {0, 3, 4}, C = {1, 3, 5}, and two edge-disjoint triangles X = {1, 3, 6}, Y = {0, 2, 4}. The union X ∪ Y covers 6 vertices, strictly more than the 5 vertices covered by A ∪ B, but X shares an edge with C, preventing a two-triangle swap in the packing. Finite exhaustive computation (decide) verifies the clique, containment, disjointness, and cover properties, and confirms maximality by showing that every triangle in the graph shares at least two vertices with A, B, or C.
The graph swapGraph604 is well-defined as a simple graph: its adjacency relation is symmetric and loopless.
Adjacency between distinct vertices x and y is defined by membership of (x,y) or (y,x) in the list swapEdges604. Reversing an edge preserves adjacency by symmetry of disjunction, and looplessness holds because x ≠ x is false.
symm := ⟨by intro x y h; exact ⟨h.1.symm, h.2.symm⟩⟩ loopless := ⟨by intro x h; exact h.1 rfl⟩
Every triangle in swapGraph604 shares at least two vertices with {0, 1, 2}, {0, 3, 4}, or {1, 3, 5}. automation
The theorem swap_maximal604 is verified by the decide tactic, which exhaustively checks all triples of vertices in Fin 7.
decideThe triangles A = {0, 1, 2}, B = {0, 3, 4}, C = {1, 3, 5}, X = {1, 3, 6}, and Y = {0, 2, 4} satisfy all individual clique, edge-disjointness, vertex containment, cardinality, and edge conflict properties. automation
The theorem swap_facts604 is verified by the decide tactic, which computes the 13 finite Boolean conjunctions establishing that A, B, C, X, Y are 3-cliques, that their intersections are pairwise at most singletons, that X and Y lie in the union of A ∪ B and the vertices outside the packing, that |A ∪ B| < |X ∪ Y|, and that |X ∩ C| ≥ 2.
decideEvery triangle in swapGraph604 contains at least one of the edges {0, 1}, {0, 4}, or {1, 3}. automation
The theorem swap_cover604 is verified by the decide tactic, checking exhaustively that the three edges form a triangle cover.
decideInstantiating swapGraph604 and the five triangles satisfies all existential conditions of the counterexample except the maximality of {A, B, C}.
We provide swapGraph604 and the triangles A = {0, 1, 2}, B = {0, 3, 4}, C = {1, 3, 5}, X = {1, 3, 6}, and Y = {0, 2, 4} as witnesses. Unpacking swap_facts604 provides the proofs of cliquehood, edge-disjointness, vertex containment, strict vertex gain, and the edge conflict with C. Supplying swap_cover604 establishes the three-edge triangle cover, leaving only the maximality of {A, B, C} to be proved.
uses
swap_facts604,swap_cover604refine ⟨swapGraph604, {0,1,2}, {0,3,4}, {1,3,5}, {1,3,6}, {0,2,4}, ?_⟩ rcases swap_facts604 with ⟨hA,hB,hC,hAB,hAC,hBC,hX,hY,hXY,hsubX,hsubY,hmore,hconf⟩ refine ⟨hA,hB,hC,hAB,hAC,hBC,hX,hY,hXY,hsubX,hsubY,hmore,hconf, ?_, swap_cover604⟩
Any 3-clique t in swapGraph604 can be written as {a, b, c} for three pairwise distinct vertices a, b, c.
Let t be a 3-clique. By definition, its cardinality is 3, so Finset.card_eq_three.mp represents t as {a, b, c} with a ≠ b, a ≠ c, and b ≠ c.
uses
Finset.card_eq_three.mpintro t ht obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp ht.card_eq
The packing {A, B, C} is maximal: every triangle t = {a, b, c} shares at least two vertices with A, B, or C.
Because t = {a, b, c} is a clique, its three pairs of distinct vertices are edges in the graph (established by ht.isClique, with simp verifying membership in t). Applying the exhaustive verification lemma swap_maximal604 completes the proof that t shares at least two vertices with A, B, or C.
uses
swap_maximal604exact swap_maximal604 a b c (ht.isClique (by simp) (by simp) hab) (ht.isClique (by simp) (by simp) hac) (ht.isClique (by simp) (by simp) hbc)
swap_maximal604- Every triangle in swapGraph604 shares at least two vertices with {0, 1, 2}, {0, 3, 4}, or {1, 3, 5}.
swap_facts604- The triangles A = {0, 1, 2}, B = {0, 3, 4}, C = {1, 3, 5}, X = {1, 3, 6}, and Y = {0, 2, 4} are 3-cliques in swapGraph604, A, B, C are edge-disjoint, X and Y are edge-disjoint, X and Y are subsets of (univ \ (A ∪ B ∪ C)) ∪ A ∪ B, |A ∪ B| < |X ∪ Y|, and |X ∩ C| ≥ 2.
swap_cover604- Every triangle in swapGraph604 contains at least one of the three edges {0, 1}, {0, 4}, or {1, 3}.
Finset.card_eq_three.mp- A finite set has cardinality 3 if and only if it consists of three distinct elements.
- The auxiliary lemmas swap_maximal604, swap_facts604, and swap_cover604 are proved entirely by Lean's decide tactic via exhaustive finite computation over all vertices and subsets of the 7-vertex graph.
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 4000000def swapEdges604 : List (Fin 7 × Fin 7) := [(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,5),(1,6), (2,4),(3,4),(3,5),(3,6)]def swapGraph604 : SimpleGraph (Fin 7) where Adj x y := x ≠ y ∧ ((x,y) ∈ swapEdges604 ∨ (y,x) ∈ swapEdges604) symm := ⟨by intro x y h; exact ⟨h.1.symm, h.2.symm⟩⟩ loopless := ⟨by intro x h; exact h.1 rfl⟩instance : DecidableRel swapGraph604.Adj := fun x y => inferInstanceAs (Decidable (x ≠ y ∧ _))theorem swap_maximal604 : ∀ a b c : Fin 7, swapGraph604.Adj a b → swapGraph604.Adj a c → swapGraph604.Adj b c → 2 ≤ (({0,1,2} : Finset (Fin 7)) ∩ {a,b,c}).card ∨ 2 ≤ (({0,3,4} : Finset (Fin 7)) ∩ {a,b,c}).card ∨ 2 ≤ (({1,3,5} : Finset (Fin 7)) ∩ {a,b,c}).card := by decidetheorem swap_facts604 : swapGraph604.IsNClique 3 ({0,1,2} : Finset (Fin 7)) ∧ swapGraph604.IsNClique 3 ({0,3,4} : Finset (Fin 7)) ∧ swapGraph604.IsNClique 3 ({1,3,5} : Finset (Fin 7)) ∧ (({0,1,2} : Finset (Fin 7)) ∩ {0,3,4}).card ≤ 1 ∧ (({0,1,2} : Finset (Fin 7)) ∩ {1,3,5}).card ≤ 1 ∧ (({0,3,4} : Finset (Fin 7)) ∩ {1,3,5}).card ≤ 1 ∧ swapGraph604.IsNClique 3 ({1,3,6} : Finset (Fin 7)) ∧ swapGraph604.IsNClique 3 ({0,2,4} : Finset (Fin 7)) ∧ (({1,3,6} : Finset (Fin 7)) ∩ {0,2,4}).card ≤ 1 ∧ (({1,3,6} : Finset (Fin 7)) ⊆ (Finset.univ \ (({0,1,2} : Finset (Fin 7)) ∪ {0,3,4} ∪ {1,3,5})) ∪ {0,1,2} ∪ {0,3,4}) ∧ (({0,2,4} : Finset (Fin 7)) ⊆ (Finset.univ \ (({0,1,2} : Finset (Fin 7)) ∪ {0,3,4} ∪ {1,3,5})) ∪ {0,1,2} ∪ {0,3,4}) ∧ (({0,1,2} : Finset (Fin 7)) ∪ {0,3,4}).card < (({1,3,6} : Finset (Fin 7)) ∪ {0,2,4}).card ∧ 2 ≤ (({1,3,6} : Finset (Fin 7)) ∩ {1,3,5}).card := by decidetheorem swap_cover604 : ∀ a b c : Fin 7, swapGraph604.Adj a b → swapGraph604.Adj a c → swapGraph604.Adj b c → ((0 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7)) ∧ (1 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7))) ∨ ((0 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7)) ∧ (4 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7))) ∨ ((1 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7)) ∧ (3 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7))) := by decidetheorem finite_maximal_packing_two_triangle_swap_counterexample : ∃ (G : SimpleGraph (Fin 7)) (A B C X Y : Finset (Fin 7)), G.IsNClique 3 A ∧ G.IsNClique 3 B ∧ G.IsNClique 3 C ∧ (A ∩ B).card ≤ 1 ∧ (A ∩ C).card ≤ 1 ∧ (B ∩ C).card ≤ 1 ∧ G.IsNClique 3 X ∧ G.IsNClique 3 Y ∧ (X ∩ Y).card ≤ 1 ∧ X ⊆ (Finset.univ \ (A ∪ B ∪ C)) ∪ A ∪ B ∧ Y ⊆ (Finset.univ \ (A ∪ B ∪ C)) ∪ A ∪ B ∧ (A ∪ B).card < (X ∪ Y).card ∧ 2 ≤ (X ∩ C).card ∧ (∀ t : Finset (Fin 7), G.IsNClique 3 t → 2 ≤ (A ∩ t).card ∨ 2 ≤ (B ∩ t).card ∨ 2 ≤ (C ∩ t).card) ∧ (∀ a b c : Fin 7, G.Adj a b → G.Adj a c → G.Adj b c → ((0 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7)) ∧ (1 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7))) ∨ ((0 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7)) ∧ (4 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7))) ∨ ((1 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7)) ∧ (3 : Fin 7) ∈ ({a,b,c} : Finset (Fin 7)))) := by refine ⟨swapGraph604, {0,1,2}, {0,3,4}, {1,3,5}, {1,3,6}, {0,2,4}, ?_⟩ rcases swap_facts604 with ⟨hA,hB,hC,hAB,hAC,hBC,hX,hY,hXY,hsubX,hsubY,hmore,hconf⟩ refine ⟨hA,hB,hC,hAB,hAC,hBC,hX,hY,hXY,hsubX,hsubY,hmore,hconf, ?_, swap_cover604⟩ intro t ht obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp ht.card_eq exact swap_maximal604 a b c (ht.isClique (by simp) (by simp) hab) (ht.isClique (by simp) (by simp) hac) (ht.isClique (by simp) (by simp) hbc)