AFTD Auto-Formalizing Theoretical Domains

simple_graph_pendant_triple_expand_leaf_adj

theoremverified

Each added leaf is adjacent exactly to its corresponding fresh internal path vertex.

Statement

theorem simple_graph_pendant_triple_expand_leaf_adj {V : Type*}
    (G : SimpleGraph V) (u v : V) (p : V ⊕ Fin 6) (i : Fin 3) :
    (simple_graph_pendant_triple_expand G u v).Adj p (Sum.inr (i.addNat 3)) ↔
      p = Sum.inr (i.castAdd 3)
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…
Used by 1

The proof, explained

We perform a case analysis on whether the vertex $p \in V \oplus \operatorname{Fin} 6$ belongs to the original vertex set $V$ or to the added vertices $\operatorname{Fin} 6$. When $p \in V$, both sides of the equivalence are false: an original vertex cannot equal an added vertex, and no edges connect $V$ to any of the three pendant leaves. When $p \in \operatorname{Fin} 6$, an exhaustive verification over all 18 combinations of $i \in \operatorname{Fin} 3$ and $j \in \operatorname{Fin} 6$ confirms that leaf $i + 3$ is adjacent to $j$ if and only if $j = i$.

  1. The equivalence holds when $p$ is an original vertex in $V$ (both sides are false).

    We split on whether the vertex $p \in V \oplus \operatorname{Fin} 6$ comes from $V$ or $\operatorname{Fin} 6$. If $p = \operatorname{inl}(a)$ for some $a \in V$, the right-hand side $p = \operatorname{inr}(i)$ is false because the sum injections have disjoint images. For the left-hand side, `fin_cases i` enumerates the three cases $i \in \{0, 1, 2\}$. In each case, simplifying with the definition of the triple expansion shows that none of the added edges incident to leaf $\operatorname{inr}(i + 3)$ connect to any vertex in $V$, so the left-hand side is also false. Thus both sides are false, and the equivalence holds.

    lines 5–9

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

      cases p with
      | inl a =>
        fin_cases i <;>
          simp [simple_graph_pendant_triple_expand, SimpleGraph.map_adj,
            SimpleGraph.fromEdgeSet_adj, Sym2.eq_iff]
  2. The equivalence holds when $p$ is one of the added vertices in $\operatorname{Fin} 6$.

    If $p = \operatorname{inr}(j)$ for some $j \in \operatorname{Fin} 6$, `fin_cases` exhaustively tests all $3 \times 6 = 18$ combinations of $i \in \operatorname{Fin} 3$ and $j \in \operatorname{Fin} 6$. For each combination, `simp` evaluates the edge set of the triple expansion: the leaf $\operatorname{inr}(i + 3)$ is adjacent to $\operatorname{inr}(j)$ if and only if $j = i$ (that is, leaf 3 is adjacent only to 0, leaf 4 only to 1, and leaf 5 only to 2). This matches the right-hand side condition $j = i$.

    lines 10–13

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

      | inr j =>
        fin_cases i <;> fin_cases j <;>
          simp [simple_graph_pendant_triple_expand, SimpleGraph.map_adj,
            SimpleGraph.fromEdgeSet_adj, Sym2.eq_iff]
SimpleGraph.map_adj
In the image of a graph under an embedding, two vertices are adjacent if and only if they are the images of adjacent vertices in the source graph.
SimpleGraph.fromEdgeSet_adj
In a graph constructed from an edge set, two vertices are adjacent if and only if they are distinct and the unordered pair between them belongs to the edge set.
Sym2.eq_iff
Two unordered pairs $\{x, y\}$ and $\{z, w\}$ are equal if and only if $(x = z \wedge y = w)$ or $(x = w \wedge 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_leaf_adj {V : Type*}    (G : SimpleGraph V) (u v : V) (p : V ⊕ Fin 6) (i : Fin 3) :    (simple_graph_pendant_triple_expand G u v).Adj p (Sum.inr (i.addNat 3)) ↔      p = Sum.inr (i.castAdd 3) := by  cases p with  | inl a =>    fin_cases i <;>      simp [simple_graph_pendant_triple_expand, SimpleGraph.map_adj,        SimpleGraph.fromEdgeSet_adj, Sym2.eq_iff]  | inr j =>    fin_cases i <;> fin_cases j <;>      simp [simple_graph_pendant_triple_expand, SimpleGraph.map_adj,        SimpleGraph.fromEdgeSet_adj, Sym2.eq_iff]
See it in the graphDiscuss this resultChallenge it