op223_tree_adjacent_shift_other_degrees
An adjacent generalized shift in a finite tree preserves the degree of every vertex other than its two endpoints.
Statement
theorem op223_tree_adjacent_shift_other_degrees {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (u v : V) (hT : T.IsTree) (huv : T.Adj u v) : ∀ x : V, x ≠ u → x ≠ v → Nat.card ((gts_graph T u v u).neighborSet x) = Nat.card (T.neighborSet x)
- Source
- arXiv:2610.17078 Open Problem 6.1; corrected versions of auxiliary statements retired by experiments 23031 and 23032
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- gts_graphThe graph obtained from T by deleting all edges between candidate v and its neighbours other than w, and inserting edges between…
- Used by 1
- op223_tree_adjacent_shift_nonleaf_countIf both endpoints of an edge of a finite tree have degree at least two, shifting along that edge reduces the number of non-leaf vertices…
The proof, explained
An adjacent generalized tree shift from vertex v to an adjacent vertex u redirects all edges incident to v (except the edge {u, v}) to vertex u. For any vertex x other than u and v, we distinguish two cases based on whether x was adjacent to v. If x is not adjacent to v, no edge incident to x is modified, so its degree is unchanged. If x is adjacent to v, the acyclicity of the tree prevents x from also being adjacent to u (avoiding a triangle); consequently, the shift deletes the single edge {v, x} and adds the single edge {u, x}, exactly preserving the degree of x.
In a tree, two vertices adjacent to a common neighbor cannot be adjacent to each other (trees contain no triangles).
Suppose for contradiction that u is adjacent to x, where u ~ v and v ~ x. Composing these edges produces a path p = [u, v, x] from u to x (SimpleGraph.Walk.cons_isPath_iff, SimpleGraph.Walk.IsPath.nil). In an acyclic graph, any path from u to x starting with an edge to a neighbor must have that neighbor as its second vertex, forcing x = v (SimpleGraph.Walk.snd_cons, SimpleGraph.Walk.end_mem_support). This contradicts that v and x are adjacent, which requires v ≠ x.
uses
SimpleGraph.Walk.cons_isPath_iff,SimpleGraph.Walk.IsPath.nil,SimpleGraph.Walk.end_mem_support,SimpleGraph.Walk.snd_consprivate lemma op223_tree_adjacent_shift_other_degrees_no_triangle {V : Type*} (T : SimpleGraph V) {u v x : V} (hT : T.IsTree) (huv : T.Adj u v) (hvx : T.Adj v x) : ¬ T.Adj u x := by intro hux have h1 : (SimpleGraph.Walk.cons hvx SimpleGraph.Walk.nil : T.Walk v x).IsPath := by rw [SimpleGraph.Walk.cons_isPath_iff] exact ⟨SimpleGraph.Walk.IsPath.nil, by simp [hvx.ne]⟩ have hp : (SimpleGraph.Walk.cons huv (SimpleGraph.Walk.cons hvx SimpleGraph.Walk.nil)).IsPath := by rw [SimpleGraph.Walk.cons_isPath_iff] refine ⟨h1, ?_⟩ simp [huv.ne, hux.ne] have key := hT.isAcyclic.eq_snd_of_adj_start (p := SimpleGraph.Walk.cons huv (SimpleGraph.Walk.cons hvx SimpleGraph.Walk.nil)) hp hux (SimpleGraph.Walk.end_mem_support _) rw [SimpleGraph.Walk.snd_cons] at key exact hvx.ne' key
For any vertex x ∉ {u, v}, an edge {x, y} is in the set of edges to be deleted from v if and only if y = v and v is adjacent to x.
The deleted edges are those of the form {v, z} where v ~ z and z ≠ u. By the symmetry of unordered pairs (Sym2.eq_iff.mp), {x, y} = {v, z} implies either x = v and y = z, or x = z and y = v. Since x ≠ v, only the second case is possible, which forces y = v and z = x, meaning v ~ x. Conversely, if y = v and v ~ x, taking z = x witnesses that {x, y} = {v, x} is in the deleted set (Sym2.eq_swap).
uses
Sym2.eq_iff.mp,Sym2.eq_swapprivate lemma op223_tree_adjacent_shift_other_degrees_mem_del {V : Type*} (T : SimpleGraph V) (u v x y : V) (hx1 : x ≠ u) (hx2 : x ≠ v) : (∃ z : V, s(x, y) = s(v, z) ∧ T.Adj v z ∧ z ≠ u) ↔ (y = v ∧ T.Adj v x) := by constructor · rintro ⟨z, he, hadj, hzu⟩ rcases Sym2.eq_iff.mp he with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 hx2 · subst h1; subst h2; exact ⟨rfl, hadj⟩ · rintro ⟨rfl, hadj⟩ exact ⟨x, Sym2.eq_swap, hadj, hx1⟩
For any vertex x ≠ u, an edge {x, y} is in the set of edges to be added to u if and only if y = u and v is adjacent to x.
The added edges are of the form {u, z} where v ~ z and z ≠ u. By Sym2.eq_iff.mp, {x, y} = {u, z} implies either x = u or x = z. Since x ≠ u, we must have x = z and y = u, so v ~ x. Conversely, if y = u and v ~ x, taking z = x witnesses that {x, y} is in the added edge set (Sym2.eq_swap).
uses
Sym2.eq_iff.mp,Sym2.eq_swapprivate lemma op223_tree_adjacent_shift_other_degrees_mem_add {V : Type*} (T : SimpleGraph V) (u v x y : V) (hx1 : x ≠ u) : (∃ z : V, s(x, y) = s(u, z) ∧ T.Adj v z ∧ z ≠ u) ↔ (y = u ∧ T.Adj v x) := by constructor · rintro ⟨z, he, hadj, hzu⟩ rcases Sym2.eq_iff.mp he with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 hx1 · subst h1; subst h2; exact ⟨rfl, hadj⟩ · rintro ⟨rfl, hadj⟩ exact ⟨x, Sym2.eq_swap, hadj, hx1⟩
The degree equality for any vertex x ∉ {u, v} reduces to comparing set cardinalities using the characterized deleted and added edge sets.
Fix a vertex x distinct from both endpoints u and v. We convert the subtype cardinality Nat.card to the set cardinality Set.ncard using Nat.card_coe_set_eq. We then instantiate the helper characterizations of the deleted edges (op223_tree_adjacent_shift_other_degrees_mem_del) and added edges (op223_tree_adjacent_shift_other_degrees_mem_add) incident to x.
uses
Nat.card_coe_set_eq,op223_tree_adjacent_shift_other_degrees_mem_del,op223_tree_adjacent_shift_other_degrees_mem_addtheorem op223_tree_adjacent_shift_other_degrees {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (u v : V) (hT : T.IsTree) (huv : T.Adj u v) : ∀ x : V, x ≠ u → x ≠ v → Nat.card ((gts_graph T u v u).neighborSet x) = Nat.card (T.neighborSet x) := by intro x hx1 hx2 rw [Nat.card_coe_set_eq, Nat.card_coe_set_eq] have hS : ∀ y : V, (∃ z : V, s(x, y) = s(v, z) ∧ T.Adj v z ∧ z ≠ u) ↔ (y = v ∧ T.Adj v x) := fun y => op223_tree_adjacent_shift_other_degrees_mem_del T u v x y hx1 hx2 have hE : ∀ y : V, (∃ z : V, s(x, y) = s(u, z) ∧ T.Adj v z ∧ z ≠ u) ↔ (y = u ∧ T.Adj v x) := fun y => op223_tree_adjacent_shift_other_degrees_mem_add T u v x y hx1
When x is adjacent to v, x cannot be adjacent to u, and the neighbor set of x in the shifted graph is (N_T(x) \\ {v}) ∪ {u}.
We split into cases on whether v is adjacent to x. In the case where v ~ x, the absence of triangles in trees (op223_tree_adjacent_shift_other_degrees_no_triangle) guarantees that u is not adjacent to x. Unfolding the definition of adjacency in the shifted graph and simplifying with the edge characterizations (SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, SimpleGraph.mem_neighborSet, Set.mem_ofPred_eq, Set.mem_insert_iff, Set.mem_sdiff, Set.mem_singleton_iff) shows that the new neighbor set is formed by removing v and inserting u, using Or.inr and Or.inl to verify the logical equivalence.
uses
op223_tree_adjacent_shift_other_degrees_no_triangle,SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adj,SimpleGraph.fromEdgeSet_adj,SimpleGraph.mem_neighborSet,Set.mem_ofPred_eq,Set.mem_insert_iff,Set.mem_sdiff,Set.mem_singleton_iff,Or.inr,Or.inlby_cases hvx : T.Adj v x · have hne : ¬ T.Adj u x := op223_tree_adjacent_shift_other_degrees_no_triangle T hT huv hvx have hset : (gts_graph T u v u).neighborSet x = insert u (T.neighborSet x \ {v}) := by ext y simp only [gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, SimpleGraph.mem_neighborSet, Set.mem_ofPred_eq, Set.mem_insert_iff, Set.mem_sdiff, Set.mem_singleton_iff, hS y, hE y] constructor · rintro (⟨hadj, hnot⟩ | ⟨⟨rfl, -⟩, -⟩) · exact Or.inr ⟨hadj, fun hy => hnot ⟨hy, hvx⟩⟩ · exact Or.inl rfl · rintro (rfl | ⟨hadj, hyv⟩) · exact Or.inr ⟨⟨rfl, hvx⟩, hx1⟩ · exact Or.inl ⟨hadj, fun h => hyv h.1⟩ rw [hset]
When x is adjacent to v, the degree of x in the shifted graph equals its original degree in T.
Because u is not adjacent to x, u ∉ N_T(x) \\ {v}, so inserting u increases the set cardinality by 1 (Set.ncard_insert_of_notMem). Moreover, since v ~ x, v belongs to N_T(x), so removing v decreases the cardinality by 1 (Set.ncard_sdiff_singleton_add_one). These two operations cancel each other out, leaving the degree unchanged.
uses
Set.mem_sdiff,Set.mem_singleton_iff,SimpleGraph.mem_neighborSet,Set.ncard_insert_of_notMem,Set.ncard_sdiff_singleton_add_onehave hu_not : u ∉ T.neighborSet x \ {v} := by simp only [Set.mem_sdiff, Set.mem_singleton_iff, SimpleGraph.mem_neighborSet] rintro ⟨hadj, -⟩ exact hne hadj.symm rw [Set.ncard_insert_of_notMem hu_not] have hv_mem : v ∈ T.neighborSet x := (SimpleGraph.mem_neighborSet T x v).mpr hvx.symm rw [(Set.ncard_sdiff_singleton_add_one hv_mem).symm]
When x is not adjacent to v, the neighbor set of x is completely unchanged, so its degree is preserved.
When x is not adjacent to v, no edges incident to x are deleted (as deleted edges are incident to v) and no edges incident to x are added (as added edges require a neighbor of v). Unfolding the shifted graph definition and simplifying via propositional logic confirms that the neighbor set of x remains identical to N_T(x), so the degree is unchanged.
uses
SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adj,SimpleGraph.fromEdgeSet_adj,SimpleGraph.mem_neighborSet,Set.mem_ofPred_eq· have hset : (gts_graph T u v u).neighborSet x = T.neighborSet x := by ext y simp only [gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, SimpleGraph.mem_neighborSet, Set.mem_ofPred_eq, hS y, hE y] tauto rw [hset]
SimpleGraph.Walk.cons_isPath_iff- A walk formed by prepending an edge (u, v) to a walk p from v to w is a path if and only if p is a path and u is not in the support of p.
SimpleGraph.Walk.IsPath.nil- The trivial empty walk consisting of a single vertex is a path.
SimpleGraph.Walk.end_mem_support- The endpoint of a walk belongs to its support (the list of visited vertices).
SimpleGraph.Walk.snd_cons- The second vertex of the walk formed by prepending an edge (u, v) to a walk starting at v is v.
Sym2.eq_iff.mp- An equality of unordered pairs s(a, b) = s(c, d) implies that either (a = c and b = d) or (a = d and b = c).
Sym2.eq_swap- The unordered pair s(a, b) is equal to s(b, a).
Nat.card_coe_set_eq- The type-theoretic cardinality (Nat.card) of a coerced set equals its finite set cardinality (Set.ncard).
op223_tree_adjacent_shift_other_degrees_mem_del- For vertices x distinct from u and v, an edge {x, y} belongs to the deleted set of edges incident to v if and only if y = v and v is adjacent to x.
op223_tree_adjacent_shift_other_degrees_mem_add- For a vertex x distinct from u, an edge {x, y} belongs to the added set of edges incident to u if and only if y = u and v is adjacent to x.
op223_tree_adjacent_shift_other_degrees_no_triangle- In a tree, two vertices adjacent to a common neighbor cannot be adjacent to each other (trees have no triangles).
SimpleGraph.sup_adj- Two vertices are adjacent in the union of two graphs if and only if they are adjacent in the first graph or the second graph.
SimpleGraph.deleteEdges_adj- Two vertices are adjacent in a graph with deleted edges if and only if they are adjacent in the original graph and their edge is not in the deleted set.
SimpleGraph.fromEdgeSet_adj- Two vertices are adjacent in a graph constructed from an edge set if and only if their edge belongs to the set and the two vertices are distinct.
SimpleGraph.mem_neighborSet- A vertex w belongs to the neighbor set of v if and only if v and w are adjacent.
Set.mem_ofPred_eq- An element belongs to the set comprehension of a predicate if and only if the predicate holds for that element.
Set.mem_insert_iff- An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_sdiff- An element belongs to s \\ t if and only if it belongs to s and does not belong to t.
Set.mem_singleton_iff- An element belongs to the singleton set {b} if and only if it equals b.
Or.inr- From a proof of B, one can infer the disjunction A ∨ B.
Or.inl- From a proof of A, one can infer the disjunction A ∨ B.
Set.ncard_insert_of_notMem- Inserting an element not in a finite set increases its cardinality by 1.
Set.ncard_sdiff_singleton_add_one- For any element a in a finite set s, the cardinality of s \\ {a} plus 1 equals the cardinality of s.
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.
private lemma op223_tree_adjacent_shift_other_degrees_no_triangle {V : Type*} (T : SimpleGraph V) {u v x : V} (hT : T.IsTree) (huv : T.Adj u v) (hvx : T.Adj v x) : ¬ T.Adj u x := by intro hux have h1 : (SimpleGraph.Walk.cons hvx SimpleGraph.Walk.nil : T.Walk v x).IsPath := by rw [SimpleGraph.Walk.cons_isPath_iff] exact ⟨SimpleGraph.Walk.IsPath.nil, by simp [hvx.ne]⟩ have hp : (SimpleGraph.Walk.cons huv (SimpleGraph.Walk.cons hvx SimpleGraph.Walk.nil)).IsPath := by rw [SimpleGraph.Walk.cons_isPath_iff] refine ⟨h1, ?_⟩ simp [huv.ne, hux.ne] have key := hT.isAcyclic.eq_snd_of_adj_start (p := SimpleGraph.Walk.cons huv (SimpleGraph.Walk.cons hvx SimpleGraph.Walk.nil)) hp hux (SimpleGraph.Walk.end_mem_support _) rw [SimpleGraph.Walk.snd_cons] at key exact hvx.ne' keyset_option maxHeartbeats 1000000 inprivate lemma op223_tree_adjacent_shift_other_degrees_mem_del {V : Type*} (T : SimpleGraph V) (u v x y : V) (hx1 : x ≠ u) (hx2 : x ≠ v) : (∃ z : V, s(x, y) = s(v, z) ∧ T.Adj v z ∧ z ≠ u) ↔ (y = v ∧ T.Adj v x) := by constructor · rintro ⟨z, he, hadj, hzu⟩ rcases Sym2.eq_iff.mp he with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 hx2 · subst h1; subst h2; exact ⟨rfl, hadj⟩ · rintro ⟨rfl, hadj⟩ exact ⟨x, Sym2.eq_swap, hadj, hx1⟩set_option maxHeartbeats 1000000 inprivate lemma op223_tree_adjacent_shift_other_degrees_mem_add {V : Type*} (T : SimpleGraph V) (u v x y : V) (hx1 : x ≠ u) : (∃ z : V, s(x, y) = s(u, z) ∧ T.Adj v z ∧ z ≠ u) ↔ (y = u ∧ T.Adj v x) := by constructor · rintro ⟨z, he, hadj, hzu⟩ rcases Sym2.eq_iff.mp he with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 hx1 · subst h1; subst h2; exact ⟨rfl, hadj⟩ · rintro ⟨rfl, hadj⟩ exact ⟨x, Sym2.eq_swap, hadj, hx1⟩theorem op223_tree_adjacent_shift_other_degrees {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (u v : V) (hT : T.IsTree) (huv : T.Adj u v) : ∀ x : V, x ≠ u → x ≠ v → Nat.card ((gts_graph T u v u).neighborSet x) = Nat.card (T.neighborSet x) := by intro x hx1 hx2 rw [Nat.card_coe_set_eq, Nat.card_coe_set_eq] have hS : ∀ y : V, (∃ z : V, s(x, y) = s(v, z) ∧ T.Adj v z ∧ z ≠ u) ↔ (y = v ∧ T.Adj v x) := fun y => op223_tree_adjacent_shift_other_degrees_mem_del T u v x y hx1 hx2 have hE : ∀ y : V, (∃ z : V, s(x, y) = s(u, z) ∧ T.Adj v z ∧ z ≠ u) ↔ (y = u ∧ T.Adj v x) := fun y => op223_tree_adjacent_shift_other_degrees_mem_add T u v x y hx1 by_cases hvx : T.Adj v x · have hne : ¬ T.Adj u x := op223_tree_adjacent_shift_other_degrees_no_triangle T hT huv hvx have hset : (gts_graph T u v u).neighborSet x = insert u (T.neighborSet x \ {v}) := by ext y simp only [gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, SimpleGraph.mem_neighborSet, Set.mem_ofPred_eq, Set.mem_insert_iff, Set.mem_sdiff, Set.mem_singleton_iff, hS y, hE y] constructor · rintro (⟨hadj, hnot⟩ | ⟨⟨rfl, -⟩, -⟩) · exact Or.inr ⟨hadj, fun hy => hnot ⟨hy, hvx⟩⟩ · exact Or.inl rfl · rintro (rfl | ⟨hadj, hyv⟩) · exact Or.inr ⟨⟨rfl, hvx⟩, hx1⟩ · exact Or.inl ⟨hadj, fun h => hyv h.1⟩ rw [hset] have hu_not : u ∉ T.neighborSet x \ {v} := by simp only [Set.mem_sdiff, Set.mem_singleton_iff, SimpleGraph.mem_neighborSet] rintro ⟨hadj, -⟩ exact hne hadj.symm rw [Set.ncard_insert_of_notMem hu_not] have hv_mem : v ∈ T.neighborSet x := (SimpleGraph.mem_neighborSet T x v).mpr hvx.symm rw [(Set.ncard_sdiff_singleton_add_one hv_mem).symm] · have hset : (gts_graph T u v u).neighborSet x = T.neighborSet x := by ext y simp only [gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, SimpleGraph.mem_neighborSet, Set.mem_ofPred_eq, hS y, hE y] tauto rw [hset]