AFTD Auto-Formalizing Theoretical Domains

finite_maximal_packing_two_triangle_swap_counterexample

theoremverified

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

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.

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

    lines 9–10

      symm := ⟨by intro x y h; exact ⟨h.1.symm, h.2.symm⟩⟩
      loopless := ⟨by intro x h; exact h.1 rfl⟩
  2. 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.

    line 18

      decide
  3. The 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.

    line 37

      decide
  4. Every 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.

    line 44

      decide
  5. Instantiating 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.

    lines 60–62

    uses swap_facts604, swap_cover604

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

    lines 63–64

    uses Finset.card_eq_three.mp

      intro t ht
      obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp ht.card_eq
  7. 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.

    lines 65–68

    uses swap_maximal604

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

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