AFTD Auto-Formalizing Theoretical Domains

simple_graph_pair_stable_k4_link_two_attachment_sharp

theoremverified

A two-edge-stable graph can contain a four-clique and a distinguished clique vertex for which one face vertex has no external common neighbor with the distinguished vertex.

Statement

theorem simple_graph_pair_stable_k4_link_two_attachment_sharp : ∃ (G : SimpleGraph (Fin 8)) (x a b c : Fin 8),
    (∀ e f : Sym2 (Fin 8), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f →
      simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) ∧
    G.IsNClique 4 ({x,a,b,c} : Finset (Fin 8)) ∧
    (∀ y : Fin 8, y ∉ ({x,a,b,c} : Finset (Fin 8)) → G.Adj x y → ¬ G.Adj c y)
Source
The already certified eight-vertex pair-stable graph supplies a sharpness example for the K4 link-extension lemma.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The theorem is proved by exhibiting an explicit 8-vertex graph `In701CE.G` and choosing vertices $x=0, a=2, b=7, c=4$. Two-edge stability of this graph is established by the pre-proved lemma `In701CE.stable`, while the remaining conditions—that $\{0, 2, 7, 4\}$ spans a 4-clique and that $0$ and $4$ share no common external neighbor—are verified by finite exhaustive computation using `decide +kernel`.

  1. The graph `In701CE.G` and the vertices $x=0, a=2, b=7, c=4$ satisfy the two-edge-stability property, reducing the theorem to checking clique membership and the nonexistence of an external common neighbor.

    We provide the explicit 8-vertex graph `In701CE.G` and vertex choices $x=0, a=2, b=7, c=4$ to instantiate the existential quantifier. The first condition, that deleting any two distinct edges from `In701CE.G` preserves the triangle packing number, is supplied directly by `In701CE.stable`. This leaves two subgoals: verifying that $\{0, 2, 7, 4\}$ is a 4-clique and that vertices $0$ and $4$ have no common neighbor outside this set.

    line 8

    uses In701CE.stable

      refine ⟨In701CE.G,0,2,7,4,In701CE.stable,?_,?_⟩
  2. The set $\{0, 2, 7, 4\}$ forms a 4-clique in `In701CE.G`. automation

    The goal requires showing that all four vertices are pairwise distinct and adjacent in `In701CE.G`. Since `In701CE.G` is a concrete graph on `Fin 8`, this is a finite decidable property verified by kernel computation.

    line 9

      · decide +kernel
  3. Vertices $0$ and $4$ have no common neighbor outside $\{0, 2, 7, 4\}$. automation

    The goal requires showing that for every vertex $y \in \text{Fin } 8 \setminus \{0, 2, 7, 4\}$, if $y$ is adjacent to $0$, then $y$ is not adjacent to $4$. This universally quantified property over the remaining four vertices is decidable and checked exhaustively by kernel computation.

    line 10

      · decide +kernel
In701CE.stable
In the graph `In701CE.G`, deleting any two distinct edges leaves the triangle packing number unchanged.

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_k4_link_two_attachment_sharp : ∃ (G : SimpleGraph (Fin 8)) (x a b c : Fin 8),    (∀ e f : Sym2 (Fin 8), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f →      simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) ∧    G.IsNClique 4 ({x,a,b,c} : Finset (Fin 8)) ∧    (∀ y : Fin 8, y ∉ ({x,a,b,c} : Finset (Fin 8)) → G.Adj x y → ¬ G.Adj c y) := by  refine ⟨In701CE.G,0,2,7,4,In701CE.stable,?_,?_⟩  · decide +kernel  · decide +kernel
See it in the graphDiscuss this resultChallenge it