op223_adjacent_is_generalized_tree_shift
For any tree T and any adjacent vertices u, v, the graph gts_graph T u v u obtained by shifting all neighbours of v other than u to u is a generalized tree shift of T.
Statement
theorem op223_adjacent_is_generalized_tree_shift {V : Type*} (T : SimpleGraph V) (hT : T.IsTree) (u v : V) (huv : T.Adj u v) : is_generalized_tree_shift T (gts_graph T u v u)
- Source
- step towards nonsustainable_tree_has_nonsustainable_successor_closer_to_star
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- gts_graphThe graph obtained from T by deleting all edges between candidate v and its neighbours other than w, and inserting edges between…
- is_generalized_tree_shiftA simple graph T' on an arbitrary type V is obtained from a tree T by a generalized tree shift if T is a tree, and there exist distinct…
- Used by 1
- op223_shift_bad_edge_yields_stepIf a nonsustainable tree undergoes an adjacent shift and a retained beneficiary edge remains nonsustainable, the shift is a step between…
The proof, explained
A generalized tree shift along a path p from u to v shifts all neighbors of v other than p's penultimate vertex to u, requiring that all internal vertices of p have degree 2 in T. When u and v are already adjacent, the single edge (u, v) is chosen as the path. This path of length 1 has no internal vertices, making the degree condition vacuously true, and its penultimate vertex is u, which matches the definition of gts_graph T u v u.
It suffices to check the generalized tree shift conditions using the single-edge walk from u to v as the witness path.
The definition of is_generalized_tree_shift requires a tree T, two distinct vertices u and v, and a path between them whose internal vertices have degree 2, such that the shifted graph matches gts_graph with the penultimate vertex of the path. We provide the tree hypothesis hT, vertices u and v, and the single-edge walk SimpleGraph.Walk.cons huv SimpleGraph.Walk.nil from u to v. The vertices u and v are distinct because adjacent vertices in a simple graph are never equal (huv.ne). This reduces the goal to three remaining obligations: the walk is a path, its internal vertices have degree 2, and the resulting shift matches the definition.
uses
SimpleGraph.Walk.cons,SimpleGraph.Walk.nilrefine ⟨hT, u, v, SimpleGraph.Walk.cons huv SimpleGraph.Walk.nil, ?_, huv.ne, ?_, ?_⟩The single-edge walk from u to v is a path.
The trivial walk at v is a path, and prepending the edge from u to v yields a path provided u is not in the support of the trivial walk (which consists solely of v). Since u ≠ v by the adjacency hypothesis, this non-membership condition holds, confirming the single-edge walk is a path.
uses
SimpleGraph.Walk.IsPath.nil.cons· exact SimpleGraph.Walk.IsPath.nil.cons (by simpa using huv.ne)
All internal vertices of the walk have degree 2 in T.
An internal vertex x on the path would have to be in the walk's support while satisfying x ≠ u and x ≠ v. Simplifying the support of the single-edge walk shows that it contains only u and v (x = u ∨ x = v). Both cases contradict the distinctness assumptions x ≠ u and x ≠ v, so the degree condition is vacuously satisfied.
uses
SimpleGraph.Walk.support_cons,SimpleGraph.Walk.support_nil,List.mem_cons,List.not_mem_nil,or_false· intro x hx hxu hxv simp only [SimpleGraph.Walk.support_cons, SimpleGraph.Walk.support_nil, List.mem_cons, List.not_mem_nil, or_false] at hx rcases hx with rfl | rfl <;> contradiction
The penultimate vertex of the single-edge walk is u, so the graph matches the definition.
For a walk consisting of a single edge from u to v, the penultimate vertex is definitionally u. Thus, the target graph gts_graph T u v u is definitionally equal to gts_graph T u v (Walk.cons huv Walk.nil).penultimate, closing the proof by reflexivity.
· rfl
SimpleGraph.Walk.cons- Extends a walk by prepending an edge between adjacent vertices.
SimpleGraph.Walk.nil- The trivial walk of length 0 from a vertex to itself.
SimpleGraph.Walk.IsPath.nil.cons- Extending the trivial walk at v by an edge from u to v yields a path, provided u does not belong to the support of the trivial walk (i.e., u ≠ v).
SimpleGraph.Walk.support_cons- The vertex support of a walk prepended with an edge from u to v starts with u followed by the support of the rest of the walk.
SimpleGraph.Walk.support_nil- The vertex support of the trivial walk at vertex u is the singleton list [u].
List.mem_cons- An element belongs to the list b :: l if and only if it equals b or belongs to l.
List.not_mem_nil- The empty list contains no elements.
or_false- Disjoining a proposition with False is equivalent to the proposition itself.
- On paper, a single edge is self-evidently a path with no internal vertices. In Lean, establishing that there are no internal vertices requires explicitly expanding the vertex support of the single-edge walk and refuting both endpoints by contradiction.
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 SimpleGraph/-- For any tree T and any adjacent vertices u, v, the graph gts_graph T u v u obtained by shifting all neighbours of v other than u to u is a generalized tree shift of T. -/theorem op223_adjacent_is_generalized_tree_shift {V : Type*} (T : SimpleGraph V) (hT : T.IsTree) (u v : V) (huv : T.Adj u v) : is_generalized_tree_shift T (gts_graph T u v u) := by refine ⟨hT, u, v, SimpleGraph.Walk.cons huv SimpleGraph.Walk.nil, ?_, huv.ne, ?_, ?_⟩ · exact SimpleGraph.Walk.IsPath.nil.cons (by simpa using huv.ne) · intro x hx hxu hxv simp only [SimpleGraph.Walk.support_cons, SimpleGraph.Walk.support_nil, List.mem_cons, List.not_mem_nil, or_false] at hx rcases hx with rfl | rfl <;> contradiction · rfl