AFTD Auto-Formalizing Theoretical Domains

simple_graph_opposite_pair_stable_k4_attachment

theoremverified

Let P be a maximum edge-disjoint triangle packing containing abc, and let x complete abc to a four-clique. Suppose neither ax nor bx is an edge of any packed triangle. If deleting the opposite edges ab and cx preserves the packing number, then another triangle t of P contains a vertex y outside the four-clique and either t contains a or b and xy is an edge, or t contains x and ay or by is an edge.

Statement

theorem simple_graph_opposite_pair_stable_k4_attachment (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (a b c x : Fin n) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (hstable : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) = simple_graph_triangle_packing_number G) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset (Fin n)) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y)))
Source
Structural reduction of the pair-stable forced-K4 branch of simple_graph_triangle_cover_number_le_two_mul_packing_number.
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

To find the required triangle attachment in P, we exploit the stability assumption: deleting the opposite edges ab and cx yields a subgraph H with the same triangle packing number. A maximum triangle packing Q in H is also a maximum packing in G, so both P and Q edge-cover all triangles of G. Since the edges ab and cx were deleted, no triangle in Q contains both endpoints of either edge; combined with the hypothesis that P avoids ax and bx, the two-cover attachment lemma simple_graph_k4_attachment_of_two_triangle_edge_covers supplies the desired triangle in P.

  1. Define H as G without the edges ab and cx, and observe H ≤ G.

    We construct H by deleting the two opposite edges from G and note that H is a subgraph of G by SimpleGraph.deleteEdges_le.

    lines 18–20

    uses SimpleGraph.deleteEdges_le

      classical
      let H := G.deleteEdges {s(a,b), s(c,x)}
      have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(a,b), s(c,x)}
  2. There exists a maximum edge-disjoint triangle packing Q in H.

    The set of sizes of edge-disjoint triangle packings in H is nonempty (the empty packing has size 0) and bounded above by the total number of vertex subsets. By Nat.sSup_mem, the supremum is achieved by some packing Q of triangles in H.

    lines 21–29

    uses Finset.card_le_univ, Nat.sSup_mem

      let A : Set ℕ := {k | ∃ Q : Finset (Finset (Fin n)),
        (∀ t ∈ Q, H.IsNClique 3 t) ∧
        (Q : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ Q.card = k}
      have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩
      have hbdd : BddAbove A := by
        refine ⟨Fintype.card (Finset (Fin n)), ?_⟩
        rintro k ⟨Q, _, _, rfl⟩
        exact Finset.card_le_univ Q
      obtain ⟨Q, hQH, hQpair, hQcard⟩ := Nat.sSup_mem hne hbdd
  3. Q is a triangle packing in G of size equal to the triangle packing number of G.

    Since deleting {ab, cx} preserves the packing number, |Q| = ν₃(H) = ν₃(G). Moreover, because H ≤ G, every triangle in H is also a triangle in G.

    lines 30–35

      have hQcard' : Q.card = simple_graph_triangle_packing_number G := by
        change Q.card = simple_graph_triangle_packing_number H at hQcard
        change simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G at hstable
        omega
      have hQG : ∀ t ∈ Q, G.IsNClique 3 t := by
        intro t ht; exact (hQH t ht).mono hHG
  4. Every triangle in G shares an edge with some triangle in P, and also with some triangle in Q.

    Because P and Q are both maximum edge-disjoint triangle packings in G, simple_graph_maximum_triangle_packing_edge_meets implies each of them is an edge cover of the triangles of G.

    lines 36–37

    uses simple_graph_maximum_triangle_packing_edge_meets

      have hPc := simple_graph_maximum_triangle_packing_edge_meets G P htri hdisj hmax
      have hQc := simple_graph_maximum_triangle_packing_edge_meets G Q hQG hQpair hQcard'
  5. The vertices a, b are distinct, and c, x are distinct.

    If a = b, then {a, b, c, x} has at most 3 vertices, contradicting that it induces a 4-clique. Similarly, if c = x, the set has at most 3 vertices, again contradicting that it is a 4-clique.

    lines 38–52

    uses Finset.card_le_card, Finset.card_le_three, Finset.mem_insert, Finset.mem_singleton

      have hab : a ≠ b := by
        intro h; subst b
        have hsub : ({a,a,c,x} : Finset (Fin n)) ⊆ {a,c,x} := by simp
        have hc := Finset.card_le_card hsub
        have h3 := Finset.card_le_three (a := a) (b := c) (c := x)
        have h4 := hk4.card_eq
        omega
      have hcx : c ≠ x := by
        intro h; subst x
        have hsub : ({a,b,c,c} : Finset (Fin n)) ⊆ {a,b,c} := by
          intro z hz; simp only [Finset.mem_insert, Finset.mem_singleton] at hz ⊢; aesop
        have hc := Finset.card_le_card hsub
        have h3 := Finset.card_le_three (a := a) (b := b) (c := c)
        have h4 := hk4.card_eq
        omega
  6. No triangle in Q contains both a and b, or both c and x.

    Any triangle in Q is a clique in H. If it contained both a and b, ab would be an edge in H, contradicting the deletion of ab. Likewise, it cannot contain both c and x.

    lines 53–63

    uses SimpleGraph.deleteEdges_adj.mp

      have havoid : ∀ t ∈ Q, ¬ (a ∈ t ∧ b ∈ t) ∧ ¬ (c ∈ t ∧ x ∈ t) := by
        intro t ht
        constructor
        · intro h
          have hadj : H.Adj a b := (hQH t ht).isClique h.1 h.2 hab
          have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2
          exact hnot (by simp)
        · intro h
          have hadj : H.Adj c x := (hQH t ht).isClique h.1 h.2 hcx
          have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2
          exact hnot (by simp)
  7. There exists a triangle t in P outside {a, b, c} with the specified attachment to x.

    We apply simple_graph_k4_attachment_of_two_triangle_edge_covers to G, P, Q, and the 4-clique {a, b, c, x}, using the two edge-cover properties and the avoidance conditions for P and Q.

    line 64

    uses simple_graph_k4_attachment_of_two_triangle_edge_covers

      exact simple_graph_k4_attachment_of_two_triangle_edge_covers n G P Q a b c x hk4 hPc hQc hQG hspokes havoid
  8. The main theorem simple_graph_opposite_pair_stable_k4_attachment holds.

    The main theorem follows immediately from stable_k4_attachment_in604, ignoring the extra hypothesis that {a, b, c} ∈ P.

    lines 66–67

    uses stable_k4_attachment_in604

    theorem simple_graph_opposite_pair_stable_k4_attachment (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (a b c x : Fin n) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (hstable : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) = simple_graph_triangle_packing_number G) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset (Fin n)) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y))) := by
      exact stable_k4_attachment_in604 n G P a b c x htri hdisj hmax hk4 hspokes hstable
SimpleGraph.deleteEdges_le
A subgraph obtained by deleting edges is a subgraph of the original graph.
Finset.card_le_univ
Any finite subset of a finite type has cardinality at most the cardinality of the whole type.
Nat.sSup_mem
A nonempty set of natural numbers bounded above contains its supremum.
simple_graph_maximum_triangle_packing_edge_meets
Every triangle in a graph shares at least an edge (two vertices) with some triangle in a maximum triangle packing.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to the other's.
Finset.card_le_three
A set of at most three elements has cardinality at most 3.
Finset.mem_insert
Finset membership in an inserted set is membership in the tail or equality to the head.
Finset.mem_singleton
Finset membership in a singleton is equality to the unique element.
SimpleGraph.deleteEdges_adj.mp
An edge in G.deleteEdges s is an edge of G that is not in s.
simple_graph_k4_attachment_of_two_triangle_edge_covers
Given a 4-clique with two triangle edge-covers satisfying the spoke-avoidance conditions, some triangle outside the clique connects to the fourth vertex.
stable_k4_attachment_in604
The core lemma establishing the attachment property for a maximum triangle packing with stable deletion of opposite edges in a 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

open scoped Sym2set_option maxRecDepth 10000set_option maxHeartbeats 3000000theorem stable_k4_attachment_in604    (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]    (P : Finset (Finset (Fin n))) (a b c x : Fin n)    (htri : ∀ t ∈ P, G.IsNClique 3 t)    (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1))    (hmax : P.card = simple_graph_triangle_packing_number G)    (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n)))    (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t))    (hstable : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) =      simple_graph_triangle_packing_number G) :    ∃ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) ∧ ∃ y ∈ t,      y ∉ ({a,b,c,x} : Finset (Fin n)) ∧      (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨        (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y))) := by  classical  let H := G.deleteEdges {s(a,b), s(c,x)}  have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(a,b), s(c,x)}  let A : Set ℕ := {k | ∃ Q : Finset (Finset (Fin n)),    (∀ t ∈ Q, H.IsNClique 3 t) ∧    (Q : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ Q.card = k}  have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩  have hbdd : BddAbove A := by    refine ⟨Fintype.card (Finset (Fin n)), ?_⟩    rintro k ⟨Q, _, _, rfl⟩    exact Finset.card_le_univ Q  obtain ⟨Q, hQH, hQpair, hQcard⟩ := Nat.sSup_mem hne hbdd  have hQcard' : Q.card = simple_graph_triangle_packing_number G := by    change Q.card = simple_graph_triangle_packing_number H at hQcard    change simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G at hstable    omega  have hQG : ∀ t ∈ Q, G.IsNClique 3 t := by    intro t ht; exact (hQH t ht).mono hHG  have hPc := simple_graph_maximum_triangle_packing_edge_meets G P htri hdisj hmax  have hQc := simple_graph_maximum_triangle_packing_edge_meets G Q hQG hQpair hQcard'  have hab : a ≠ b := by    intro h; subst b    have hsub : ({a,a,c,x} : Finset (Fin n)) ⊆ {a,c,x} := by simp    have hc := Finset.card_le_card hsub    have h3 := Finset.card_le_three (a := a) (b := c) (c := x)    have h4 := hk4.card_eq    omega  have hcx : c ≠ x := by    intro h; subst x    have hsub : ({a,b,c,c} : Finset (Fin n)) ⊆ {a,b,c} := by      intro z hz; simp only [Finset.mem_insert, Finset.mem_singleton] at hz ⊢; aesop    have hc := Finset.card_le_card hsub    have h3 := Finset.card_le_three (a := a) (b := b) (c := c)    have h4 := hk4.card_eq    omega  have havoid : ∀ t ∈ Q, ¬ (a ∈ t ∧ b ∈ t) ∧ ¬ (c ∈ t ∧ x ∈ t) := by    intro t ht    constructor    · intro h      have hadj : H.Adj a b := (hQH t ht).isClique h.1 h.2 hab      have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2      exact hnot (by simp)    · intro h      have hadj : H.Adj c x := (hQH t ht).isClique h.1 h.2 hcx      have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2      exact hnot (by simp)  exact simple_graph_k4_attachment_of_two_triangle_edge_covers n G P Q a b c x hk4 hPc hQc hQG hspokes havoidtheorem simple_graph_opposite_pair_stable_k4_attachment (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (a b c x : Fin n) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (hstable : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) = simple_graph_triangle_packing_number G) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset (Fin n)) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y))) := by  exact stable_k4_attachment_in604 n G P a b c x htri hdisj hmax hk4 hspokes hstable
See it in the graphDiscuss this resultChallenge it