simple_graph_pendant_triple_expand_old_adj
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}.
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.
uses
simple_graph_pendant_triple_expand,SimpleGraph.map_adj,SimpleGraph.deleteEdges_adj,SimpleGraph.fromEdgeSet_adj,Sym2.eq_iffsimp [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.
- The simplifier automatically deduces that no edge from the gadget component connects two vertices of the form `Sum.inl`, because every edge in the gadget contains at least one endpoint of the form `Sum.inr`.
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_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]