simple_graph_pendant_triple_expand_leaf_adj
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
- k99_join_compl_k2_not_adj_join_verticesIn the complete bipartite join graph K_{9,9} ∨ Compl(K_2), the two vertices in the independent set of size 2 are not adjacent to each other.
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$.
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.
uses
SimpleGraph.map_adj,SimpleGraph.fromEdgeSet_adj,Sym2.eq_iffcases p with | inl a => fin_cases i <;> simp [simple_graph_pendant_triple_expand, SimpleGraph.map_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq_iff]
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$.
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)$.
- The proof relies on finite exhaustion: `fin_cases` enumerates the values of $i \in \operatorname{Fin} 3$ and $j \in \operatorname{Fin} 6$, and `simp` evaluates the finite set memberships and equality tests by direct computation.
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.
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]