simple_graph_pair_stable_k4_link_two_attachment_sharp
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
- simple_graph_pair_stable_support_max_incidence_two_bad_packing_counterexampleThere is an eight-vertex two-edge-stable graph with a maximum triangle packing covering every vertex, in which every vertex belongs to at…
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
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`.
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.
uses
In701CE.stablerefine ⟨In701CE.G,0,2,7,4,In701CE.stable,?_,?_⟩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.
· decide +kernelVertices $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.
· decide +kernel
In701CE.stable- In the graph `In701CE.G`, deleting any two distinct edges leaves the triangle packing number unchanged.
- The construction of the graph `In701CE.G` and the verification of its pair-stability (`In701CE.stable`) are proven elsewhere in the library; this proof instantiates the existential witnesses and discharges the remaining finite clique and neighborhood checks via the kernel.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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