AFTD Auto-Formalizing Theoretical Domains

simple_graph_pair_stable_kernel_link_edge_spoke_exchange

theoremverified

For an active outside vertex of a maximum packing supported in a support-plus-one-vertex kernel, the local edge/spoke exchange guaranteed by global two-edge stability has its witness vertices inside the kernel.

Statement

theorem simple_graph_pair_stable_kernel_link_edge_spoke_exchange (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
    (P Q : Finset (Finset (Fin n))) (hPmax : P.card = simple_graph_triangle_packing_number G)
    (hQ : ∀ t ∈ Q, G.IsNClique 3 t)
    (hQdisj : (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1))
    (hQcard : Q.card = P.card) (x : Fin n) (hQsub : Q.biUnion id ⊆ insert x (P.biUnion id))
    (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f →
       simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G)
    (y : Fin n) (hy : y ∈ insert x (P.biUnion id)) (hynot : y ∉ Q.biUnion id)
    (a b w : Fin n) (hya : G.Adj y a) (hyb : G.Adj y b) (hab : G.Adj a b) (hyw : G.Adj y w) :
    ∃ u v : Fin n, u ∈ insert x (P.biUnion id) ∧ v ∈ insert x (P.biUnion id) ∧
      G.Adj y u ∧ G.Adj y v ∧ G.Adj u v ∧
      (u = a ∨ u = b ∨ v = a ∨ v = b) ∧ u ≠ w ∧ v ≠ w ∧ s(u,v) ≠ s(a,b)
Source
Exact local link transfer for the induced model in state/campaigns/triangle_reductions/outside_induced_kernel_in701.md; no novelty claim.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

To show that the exchange triangle guaranteed by two-edge stability around an outside vertex y stays inside the support-plus-one-vertex kernel {x} ∪ V(P), the proof first applies the local edge-spoke exchange lemma to obtain a new triangle {y, u, v}. Because Q is an alternate maximum triangle packing that does not contain y, any triangle containing y must lie entirely within {y} ∪ V(Q). Since both y and V(Q) are contained in {x} ∪ V(P), the witnesses u and v are forced to lie within the kernel.

  1. There exist vertices u and v forming a triangle with y that shares a vertex with {a, b}, avoids the spoke w, and whose base edge is distinct from {a, b}.

    By the global 2-edge stability hypothesis, removing any two distinct edges from G does not decrease its triangle packing number. We invoke the local vertex link edge-spoke exchange lemma at y for the triangle {y, a, b} and the incident edge yw, yielding vertices u and v adjacent to y and to each other such that {u, v} intersects {a, b}, neither u nor v is w, and {u, v} ≠ {a, b}.

    lines 15–17

    uses simple_graph_pair_stable_vertex_link_edge_spoke_exchange

      classical
      obtain ⟨u,v,hyu,hyv,huv,hmeet,huw,hvw,hne⟩ :=
        simple_graph_pair_stable_vertex_link_edge_spoke_exchange n G y hstable a b w hya hyb hab hyw
  2. The three-element set {y, u, v} is a 3-clique (triangle) in G.

    Because y, u, and v are pairwise adjacent in a simple graph (which has no self-loops), the vertices are pairwise distinct. A case analysis over all pairs of distinct elements in {y, u, v} confirms that every pair is adjacent, so {y, u, v} is indeed a 3-clique.

    lines 18–27

    uses Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton, SimpleGraph.Adj.symm

      have hneq1 : y ≠ u := hyu.ne
      have hneq2 : y ≠ v := hyv.ne
      have hneq3 : u ≠ v := huv.ne
      have ht : G.IsNClique 3 ({y,u,v} : Finset (Fin n)) := by
        constructor
        · intro r hr s hs hrs
          simp only [Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton] at hr hs
          rcases hr with rfl | rfl | rfl <;> rcases hs with rfl | rfl | rfl
          all_goals first | contradiction | assumption | exact SimpleGraph.Adj.symm (by assumption)
        · simp [hneq1,hneq2,hneq3]
  3. The entire triangle {y, u, v} is contained in the kernel {x} ∪ V(P).

    Since |Q| = |P| = ν(G), the packing Q is a maximum triangle packing. Because y is outside the vertex support of Q, any triangle containing y must be contained in {y} ∪ V(Q). Since y is in {x} ∪ V(P) and the vertex support of Q is already a subset of {x} ∪ V(P), it follows that {y} ∪ V(Q) ⊆ {x} ∪ V(P), which places {y, u, v} inside the kernel.

    lines 28–30

    uses simple_graph_maximum_packing_outside_triangles_inside_support, Finset.insert_subset_iff.mpr

      have hQmax : Q.card = simple_graph_triangle_packing_number G := hQcard.trans hPmax
      have hsub := simple_graph_maximum_packing_outside_triangles_inside_support n G Q hQ hQdisj hQmax y hynot {y,u,v} ht (by simp)
      have hsubW := hsub.trans (Finset.insert_subset_iff.mpr ⟨hy,hQsub⟩)
  4. The vertices u and v provide the desired exchange witnesses inside the kernel.

    Because {y, u, v} is contained in {x} ∪ V(P), both u and v belong to the kernel. Together with the adjacency, link intersection, spoke avoidance, and edge distinctness properties established in the first step, u and v satisfy all requirements of the theorem.

    line 31

      exact ⟨u,v,hsubW (by simp),hsubW (by simp),hyu,hyv,huv,hmeet,huw,hvw,hne⟩
simple_graph_pair_stable_vertex_link_edge_spoke_exchange
In a 2-edge-stable graph, given a triangle containing vertex x and another edge incident to x, there exists another triangle containing x that shares a vertex with the base of the first triangle, avoids the other incident edge, and does not share both base vertices.
Finset.mem_coe
An element belongs to the coercion of a finite set to a set if and only if it belongs to the finite set.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it equals a.
SimpleGraph.Adj.symm
Adjacency in a simple graph is symmetric: if u is adjacent to v, then v is adjacent to u.
simple_graph_maximum_packing_outside_triangles_inside_support
If P is a maximum triangle packing and x lies outside the vertex support of P, then any triangle containing x is entirely contained in {x} ∪ V(P).
Finset.insert_subset_iff.mpr
If an element a belongs to t and a finite set s is a subset of t, then insert a s is also a subset of t.

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 Sym2theorem simple_graph_pair_stable_kernel_link_edge_spoke_exchange (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]    (P Q : Finset (Finset (Fin n))) (hPmax : P.card = simple_graph_triangle_packing_number G)    (hQ : ∀ t ∈ Q, G.IsNClique 3 t)    (hQdisj : (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1))    (hQcard : Q.card = P.card) (x : Fin n) (hQsub : Q.biUnion id ⊆ insert x (P.biUnion id))    (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f →       simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G)    (y : Fin n) (hy : y ∈ insert x (P.biUnion id)) (hynot : y ∉ Q.biUnion id)    (a b w : Fin n) (hya : G.Adj y a) (hyb : G.Adj y b) (hab : G.Adj a b) (hyw : G.Adj y w) :    ∃ u v : Fin n, u ∈ insert x (P.biUnion id) ∧ v ∈ insert x (P.biUnion id) ∧      G.Adj y u ∧ G.Adj y v ∧ G.Adj u v ∧      (u = a ∨ u = b ∨ v = a ∨ v = b) ∧ u ≠ w ∧ v ≠ w ∧ s(u,v) ≠ s(a,b) := by  classical  obtain ⟨u,v,hyu,hyv,huv,hmeet,huw,hvw,hne⟩ :=    simple_graph_pair_stable_vertex_link_edge_spoke_exchange n G y hstable a b w hya hyb hab hyw  have hneq1 : y ≠ u := hyu.ne  have hneq2 : y ≠ v := hyv.ne  have hneq3 : u ≠ v := huv.ne  have ht : G.IsNClique 3 ({y,u,v} : Finset (Fin n)) := by    constructor    · intro r hr s hs hrs      simp only [Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton] at hr hs      rcases hr with rfl | rfl | rfl <;> rcases hs with rfl | rfl | rfl      all_goals first | contradiction | assumption | exact SimpleGraph.Adj.symm (by assumption)    · simp [hneq1,hneq2,hneq3]  have hQmax : Q.card = simple_graph_triangle_packing_number G := hQcard.trans hPmax  have hsub := simple_graph_maximum_packing_outside_triangles_inside_support n G Q hQ hQdisj hQmax y hynot {y,u,v} ht (by simp)  have hsubW := hsub.trans (Finset.insert_subset_iff.mpr ⟨hy,hQsub⟩)  exact ⟨u,v,hsubW (by simp),hsubW (by simp),hyu,hyv,huv,hmeet,huw,hvw,hne⟩
See it in the graphDiscuss this resultChallenge it