AFTD Auto-Formalizing Theoretical Domains

simple_graph_pendant_triple_expand_old_adj

theoremverified

Adjacency between original vertices after triple expansion is original adjacency with uv removed.

Statement

theorem simple_graph_pendant_triple_expand_old_adj {V : Type*}
    (G : SimpleGraph V) (u v a b : V) :
    (simple_graph_pendant_triple_expand G u v).Adj (Sum.inl a) (Sum.inl b) ↔
      G.Adj a b ∧ s(a,b) ≠ s(u,v)
Source
Sanity lemma for simple_graph_pendant_triple_expand, the local reduction construction for OP-309.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_pendant_triple_expandReplace uv by the path u-0-1-2-v on three fresh internal vertices, with fresh pendant leaves 3,4,5 at 0,1,2. Other original edges remain…

The proof, explained

The proof unfolds the definition of the pendant triple expansion, which decomposes the expanded graph into the embedded edge-deleted subgraph G \ {s(u, v)} and a gadget graph on six new vertices. Because every edge in the gadget has at least one endpoint among the newly added vertices, no gadget edge connects two original vertices. The automated simplifier uses this along with the characterizations of adjacency under graph embeddings and edge deletion to conclude that the original vertices a and b remain adjacent if and only if they were adjacent in G and {a, b} ≠ {u, v}.

  1. The vertices `Sum.inl a` and `Sum.inl b` are adjacent in `simple_graph_pendant_triple_expand G u v` if and only if `G.Adj a b` and `s(a, b) ≠ s(u, v)`. automation

    Unfolding `simple_graph_pendant_triple_expand`, the graph is the union of the embedded edge-deleted graph `(G.deleteEdges {s(u, v)}).map Sum.inl` and a gadget graph constructed from seven specified edges. Because each edge in the gadget involves at least one auxiliary vertex of the form `Sum.inr k`, the gadget contains no edge connecting two vertices of the form `Sum.inl`. Therefore, adjacency between `Sum.inl a` and `Sum.inl b` comes entirely from the first component. By `SimpleGraph.map_adj` and the injectivity of `Sum.inl`, this is equivalent to adjacency between `a` and `b` in `G.deleteEdges {s(u, v)}`. By `SimpleGraph.deleteEdges_adj`, this holds if and only if `G.Adj a b` and `s(a, b) ∉ {s(u, v)}`, which is `s(a, b) ≠ s(u, v)`. The `simp` tactic performs these rewrites and disjunction simplifications in a single step.

    lines 5–6

    uses simple_graph_pendant_triple_expand, SimpleGraph.map_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq_iff

      simp [simple_graph_pendant_triple_expand, SimpleGraph.map_adj,
        SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq_iff]
simple_graph_pendant_triple_expand
Definition of the pendant triple expansion graph, formed by taking the union of the embedded edge-deleted graph G \ {s(u, v)} and a gadget graph on six auxiliary vertices.
SimpleGraph.map_adj
Two vertices in the image of a graph under an embedding f are adjacent if and only if they are the images of adjacent vertices in the original graph.
SimpleGraph.deleteEdges_adj
Two vertices are adjacent in an edge-deleted graph G.deleteEdges s if and only if they are adjacent in G and the edge between them is not in s.
SimpleGraph.fromEdgeSet_adj
Two vertices are adjacent in the graph generated by an edge set s if and only if the edge between them belongs to s and the vertices are distinct.
Sym2.eq_iff
Two unordered pairs s(x, y) and s(z, w) are equal if and only if x = z and y = w, or x = w and y = z.

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

theorem simple_graph_pendant_triple_expand_old_adj {V : Type*}    (G : SimpleGraph V) (u v a b : V) :    (simple_graph_pendant_triple_expand G u v).Adj (Sum.inl a) (Sum.inl b) ↔      G.Adj a b ∧ s(a,b) ≠ s(u,v) := by  simp [simple_graph_pendant_triple_expand, SimpleGraph.map_adj,    SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq_iff]
See it in the graphDiscuss this resultChallenge it