AFTD Auto-Formalizing Theoretical Domains

simple_graph_pair_stable_outside_kernel_five_triangles

theoremverified

In a two-edge-stable graph, every active vertex that lies in the support-plus-one-vertex kernel and outside a maximum packing supported in that kernel has five distinct incident triangles inside the kernel.

Statement

theorem simple_graph_pair_stable_outside_kernel_five_triangles (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)
    (hactive : ∃ t : Finset (Fin n), G.IsNClique 3 t ∧ y ∈ t) :
    ∃ T : Finset (Finset (Fin n)), 5 ≤ T.card ∧
      ∀ t ∈ T, G.IsNClique 3 t ∧ y ∈ t ∧ t ⊆ insert x (P.biUnion id)
Source
Outside-link finite 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

The proof takes T to be the set of all triangles in G containing y. Because G is two-edge-stable and y is active, y belongs to at least five triangles, giving |T| ≥ 5. Furthermore, since Q is a maximum triangle packing not covering y, every triangle containing y has all its other vertices in the support of Q; because both y and the support of Q are contained in the kernel {x} ∪ ⋃ P, all five or more triangles in T lie entirely within the kernel.

  1. There is a candidate set T of at least five triangles containing y, reducing the goal to showing that every triangle in T lies in the kernel {x} ∪ ⋃ P.

    We define T to be the set of all triangles in G containing y. Because G is two-edge-stable and y is active (belongs to at least one triangle), lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles implies that y belongs to at least five triangles, so |T| ≥ 5. Choosing T as the witness reduces the theorem to verifying that each t ∈ T is a triangle containing y whose vertices lie in {x} ∪ ⋃ P.

    lines 14–17

    uses simple_graph_pair_stable_active_vertex_at_least_five_triangles

      classical
      let T := (Finset.univ : Finset (Finset (Fin n))).filter (fun t => G.IsNClique 3 t ∧ y ∈ t)
      have hfive : 5 ≤ T.card := simple_graph_pair_stable_active_vertex_at_least_five_triangles n G y hstable hactive
      refine ⟨T,hfive,?_⟩
  2. Every triangle t ∈ T containing y is contained in {y} ∪ ⋃ Q.

    Let t ∈ T. By the definition of T (unpacked using Finset.mem_filter.mp), t is a triangle of G containing y. Since |Q| = |P| = ν(G), Q is also a maximum triangle packing. Because y is outside the vertex support of Q, lemma simple_graph_maximum_packing_outside_triangles_inside_support implies that the vertices of t must lie entirely within {y} ∪ ⋃ Q.

    lines 18–21

    uses Finset.mem_filter.mp, simple_graph_maximum_packing_outside_triangles_inside_support

      intro t ht
      have ht' := (Finset.mem_filter.mp ht).2
      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 t ht'.1 ht'.2
  3. Every triangle t ∈ T is contained in the kernel {x} ∪ ⋃ P, completing the proof.

    By hypothesis, y ∈ {x} ∪ ⋃ P and the support ⋃ Q is a subset of {x} ∪ ⋃ P. Lemma Finset.insert_subset_iff.mpr shows that {y} ∪ ⋃ Q ⊆ {x} ∪ ⋃ P. Since t ⊆ {y} ∪ ⋃ Q, transitivity of inclusion yields t ⊆ {x} ∪ ⋃ P, completing the proof for all triangles in T.

    line 22

    uses Finset.insert_subset_iff.mpr

      exact ⟨ht'.1,ht'.2,hsub.trans (Finset.insert_subset_iff.mpr ⟨hy,hQsub⟩)⟩
simple_graph_pair_stable_active_vertex_at_least_five_triangles
In a two-edge-stable graph, any vertex incident to at least one triangle is incident to at least five distinct triangles.
Finset.mem_filter.mp
An element belongs to a filtered finite set only if it belongs to the ambient set and satisfies the predicate.
simple_graph_maximum_packing_outside_triangles_inside_support
Given a maximum triangle packing Q in a graph and a vertex y not covered by Q, any triangle containing y is entirely contained in {y} ∪ ⋃ Q.
Finset.insert_subset_iff.mpr
If an element a belongs to s and a finite set u is a subset of s, then {a} ∪ u is a subset of s.

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_outside_kernel_five_triangles (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)    (hactive : ∃ t : Finset (Fin n), G.IsNClique 3 t ∧ y ∈ t) :    ∃ T : Finset (Finset (Fin n)), 5 ≤ T.card ∧      ∀ t ∈ T, G.IsNClique 3 t ∧ y ∈ t ∧ t ⊆ insert x (P.biUnion id) := by  classical  let T := (Finset.univ : Finset (Finset (Fin n))).filter (fun t => G.IsNClique 3 t ∧ y ∈ t)  have hfive : 5 ≤ T.card := simple_graph_pair_stable_active_vertex_at_least_five_triangles n G y hstable hactive  refine ⟨T,hfive,?_⟩  intro t ht  have ht' := (Finset.mem_filter.mp ht).2  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 t ht'.1 ht'.2  exact ⟨ht'.1,ht'.2,hsub.trans (Finset.insert_subset_iff.mpr ⟨hy,hQsub⟩)⟩
See it in the graphDiscuss this resultChallenge it