op223_tree_adjacent_shift_nonleaf_count
If 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 by exactly one.
Statement
theorem op223_tree_adjacent_shift_nonleaf_count {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (u v : V) (hT : T.IsTree) (huv : T.Adj u v) (hu : 2 ≤ Nat.card (T.neighborSet u)) (hv : 2 ≤ Nat.card (T.neighborSet v)) : (Finset.univ.filter (fun x : V => 1 < Nat.card ((gts_graph T u v u).neighborSet x))).card + 1 = (Finset.univ.filter (fun x : V => 1 < Nat.card (T.neighborSet x))).card
- 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 2
- gts_graphThe graph obtained from T by deleting all edges between candidate v and its neighbours other than w, and inserting edges between…
- op223_tree_adjacent_shift_other_degreesAn adjacent generalized shift in a finite tree preserves the degree of every vertex other than its two endpoints.
- Used by 1
- op223_star_connectivity_from_edge_preservationAssume shifting along a nonsustainable edge preserves it, shifting a branch toward the center of a nonsustainable pendant edge preserves…
The proof, explained
The proof analyzes how shifting along the edge {u, v} changes vertex degrees in a tree when both u and v initially have degree at least two. The shift transfers all neighbors of v other than u over to u, leaving v with degree 1 (a leaf) while u retains at least two neighbors (a non-leaf) and every other vertex keeps its original degree. Consequently, the set of non-leaf vertices of the original tree is the disjoint union of {v} and the set of non-leaf vertices of the shifted graph, proving that shifting decreases the number of non-leaves by exactly one.
After the shift, the neighbor set of v consists solely of u.
By definition, shifting along edge {u, v} removes all original incident edges of v except {u, v}, while newly added edges are incident to u rather than v. Checking both inclusion directions confirms that no other vertex can remain or become adjacent to v in the shifted graph, and the edge {u, v} itself survives.
uses
SimpleGraph.mem_neighborSet,SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adj,SimpleGraph.fromEdgeSet_adj,Set.mem_ofPred_eq,Set.mem_singleton_iff,Sym2.eq_iffclassical -- After the shift, the candidate `v` has exactly one neighbour, namely `u`. have hvset : (gts_graph T u v u).neighborSet v = {u} := by ext x simp only [SimpleGraph.mem_neighborSet, gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq, Set.mem_singleton_iff] constructor · rintro (⟨hTx, hdel⟩ | ⟨⟨z, hz, hvz, hzu⟩, hvx⟩) · by_contra hxu apply hdel exact ⟨x, rfl, hTx, hxu⟩ · rw [Sym2.eq_iff] at hz rcases hz with ⟨hvu, hxz⟩ | ⟨hvz', hxu⟩ · exfalso; exact huv.ne hvu.symm · exfalso; exact hvz.ne hvz' · intro hxu subst hxu left constructor · exact huv.symm · rintro ⟨z, hz, hvz, hzu⟩ rw [Sym2.eq_iff] at hz rcases hz with ⟨_, hxz⟩ | ⟨hvz', _⟩ · exfalso; exact hzu hxz.symm · exfalso; exact hvz.ne hvz'
After the shift, v has degree 1 and is no longer a non-leaf.
Since the neighbor set of v in the shifted graph is the singleton {u}, its cardinality is 1. Thus its degree is not strictly greater than 1, meaning v is now a leaf.
uses
Set.ncard_univ,Set.ncard_coehave hv1 : Nat.card ((gts_graph T u v u).neighborSet v) = 1 := by rw [hvset] rw [show Nat.card ({u} : Set V) = ({u} : Set V).ncard from by rw [← Set.ncard_univ, Set.ncard_coe]] simp have hv_not : ¬ (1 < Nat.card ((gts_graph T u v u).neighborSet v)) := by omega
After the shift, u has degree greater than 1 and therefore remains a non-leaf.
In the original tree T, vertex u has degree at least 2, so it has at least one neighbor b distinct from v. The shift removes only edges incident to v that are distinct from {u, v}, so both edges {u, v} and {u, b} survive in the shifted graph. Because v and b are distinct, u has at least two distinct neighbors after the shift, which shows that its degree remains strictly greater than 1.
uses
Nat.card_eq_fintype_card,Fintype.exists_ne_of_one_lt_card,SimpleGraph.mem_neighborSet,Subtype.ext,SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adj,Sym2.eq_iff,Set.one_lt_ncard,Set.ncard_univ,Set.ncard_coehave hu_nonleaf : 1 < Nat.card ((gts_graph T u v u).neighborSet u) := by have hcard : 1 < Fintype.card (T.neighborSet u) := by rw [← Nat.card_eq_fintype_card] omega obtain ⟨b, hb⟩ := Fintype.exists_ne_of_one_lt_card hcard ⟨v, (SimpleGraph.mem_neighborSet T u v).mpr huv⟩ have hwv : b.1 ≠ v := fun h => hb (Subtype.ext h) have hadjuv : (gts_graph T u v u).Adj u v := by rw [gts_graph, SimpleGraph.sup_adj] left rw [SimpleGraph.deleteEdges_adj] refine ⟨huv, ?_⟩ rintro ⟨z, hz, hvz, hzu⟩ rw [Sym2.eq_iff] at hz rcases hz with ⟨huv', _⟩ | ⟨huz, _⟩ · exact huv.ne huv' · exact hzu huz.symm have hadjuw : (gts_graph T u v u).Adj u b.1 := by rw [gts_graph, SimpleGraph.sup_adj] left rw [SimpleGraph.deleteEdges_adj] refine ⟨b.2, ?_⟩ rintro ⟨z, hz, hvz, hzu⟩ rw [Sym2.eq_iff] at hz rcases hz with ⟨huv', _⟩ | ⟨huz, hwv'⟩ · exact huv.ne huv' · exact hwv hwv' have hpos : 1 < ((gts_graph T u v u).neighborSet u).ncard := by rw [Set.one_lt_ncard] exact ⟨v, (SimpleGraph.mem_neighborSet _ _ _).mpr hadjuv, b.1, (SimpleGraph.mem_neighborSet _ _ _).mpr hadjuw, fun h => hwv h.symm⟩ have heq : Nat.card ((gts_graph T u v u).neighborSet u) = ((gts_graph T u v u).neighborSet u).ncard := by rw [← Set.ncard_univ, Set.ncard_coe] rw [heq] exact hpos
Every vertex x ≠ v has degree greater than 1 after the shift if and only if it had degree greater than 1 before.
If x = u, the equivalence holds because u has degree at least 2 both before (by assumption) and after the shift (by the previous step). If x is distinct from both u and v, the auxiliary theorem op223_tree_adjacent_shift_other_degrees proves that its degree is entirely unchanged by the shift.
uses
op223_tree_adjacent_shift_other_degreeshave hdegree : ∀ x : V, (x ≠ v → ((1 < Nat.card ((gts_graph T u v u).neighborSet x)) ↔ (1 < Nat.card (T.neighborSet x)))) := by intro x hxv by_cases hxu : x = u · subst hxu constructor · exact fun _ => hu · exact fun _ => hu_nonleaf · rw [op223_tree_adjacent_shift_other_degrees T u v hT huv x hxu hxv]
The set of non-leaves of T equals the set of non-leaves of the shifted graph with v inserted.
A vertex x is an original non-leaf if and only if either x = v (which had degree at least 2 by hypothesis) or x ≠ v and x was a non-leaf in T. Applying the degree equivalence for x ≠ v from the previous step, this is equivalent to x = v or x being a non-leaf in the shifted graph.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_insert,Or.inl,Or.inrhave hfilter : (Finset.univ.filter (fun x : V => 1 < Nat.card (T.neighborSet x))) = insert v (Finset.univ.filter (fun x : V => 1 < Nat.card ((gts_graph T u v u).neighborSet x))) := by ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert] constructor · intro hx by_cases hxv : x = v · exact Or.inl hxv · exact Or.inr ((hdegree x hxv).mpr hx) · intro hx rcases hx with hxv | hx · subst hxv omega · by_cases hxv : x = v · subst hxv omega · exact (hdegree x hxv).mp hx
The number of non-leaf vertices decreases by exactly one after the shift.
Because v has degree 1 after the shift, it is not an element of the set of shifted non-leaves. Writing the original non-leaf set as the insertion of v into the shifted non-leaves and applying the cardinality formula for inserting a non-member proves that the new count plus 1 equals the original count.
uses
Finset.mem_filter,Finset.mem_univ,true_and,not_lt,Finset.card_insert_of_notMemhave hmem : v ∉ Finset.univ.filter (fun x : V => 1 < Nat.card ((gts_graph T u v u).neighborSet x)) := by simp only [Finset.mem_filter, Finset.mem_univ, true_and, not_lt] omega rw [hfilter] rw [Finset.card_insert_of_notMem hmem]
Finset.card_insert_of_notMem- Inserting an element a into a finite set s not containing a yields a set of cardinality |s| + 1.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_insert- An element x belongs to insert b s if and only if x = b or x ∈ s.
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
Fintype.exists_ne_of_one_lt_card- In a finite type with more than one element, every element has another element distinct from it.
Nat.card_eq_fintype_card- For a finite type, the general cardinality Nat.card coincides with the finite cardinality Fintype.card.
Or.inl- From a proof of A, deduce the disjunction A ∨ B.
Or.inr- From a proof of B, deduce the disjunction A ∨ B.
Set.ncard_coe- The cardinality of a coerced set type equals its set cardinality ncard.
Set.ncard_univ- The number of elements in the universal set of a type equals the cardinality of the type.
Set.mem_ofPred_eq- Membership of an element x in a set comprehension {y | p(y)} is propositionally equal to p(x).
Set.mem_singleton_iff- An element x belongs to the singleton set {b} if and only if x = b.
Set.one_lt_ncard- A finite set has cardinality strictly greater than 1 if and only if it contains two distinct elements.
SimpleGraph.deleteEdges_adj- Two vertices are adjacent in 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 v and w are adjacent in the graph generated from an edge set s if and only if the edge s(v, w) is in s and v ≠ w.
SimpleGraph.mem_neighborSet- A vertex w belongs to the neighbor set of v in a graph G if and only if v and w are adjacent in G.
SimpleGraph.sup_adj- Two vertices are adjacent in the union of two graphs G₁ ⊔ G₂ if and only if they are adjacent in G₁ or in G₂.
Subtype.ext- Two elements of a subtype are equal if and only if their underlying values are equal.
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
not_lt- For elements in a linear order, ¬(a < b) is equivalent to b ≤ a.
op223_tree_adjacent_shift_other_degrees- Shifting along an edge {u, v} in a tree leaves the degree of every vertex other than u and v unchanged.
true_and- The conjunction True ∧ p simplifies to p.
- The proof uses the auxiliary theorem op223_tree_adjacent_shift_other_degrees (proved elsewhere in the knowledge base), which establishes that shifting along edge {u, v} leaves the degrees of all vertices other than u and v unchanged.
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 op223_tree_adjacent_shift_nonleaf_count {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (u v : V) (hT : T.IsTree) (huv : T.Adj u v) (hu : 2 ≤ Nat.card (T.neighborSet u)) (hv : 2 ≤ Nat.card (T.neighborSet v)) : (Finset.univ.filter (fun x : V => 1 < Nat.card ((gts_graph T u v u).neighborSet x))).card + 1 = (Finset.univ.filter (fun x : V => 1 < Nat.card (T.neighborSet x))).card := by classical -- After the shift, the candidate `v` has exactly one neighbour, namely `u`. have hvset : (gts_graph T u v u).neighborSet v = {u} := by ext x simp only [SimpleGraph.mem_neighborSet, gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq, Set.mem_singleton_iff] constructor · rintro (⟨hTx, hdel⟩ | ⟨⟨z, hz, hvz, hzu⟩, hvx⟩) · by_contra hxu apply hdel exact ⟨x, rfl, hTx, hxu⟩ · rw [Sym2.eq_iff] at hz rcases hz with ⟨hvu, hxz⟩ | ⟨hvz', hxu⟩ · exfalso; exact huv.ne hvu.symm · exfalso; exact hvz.ne hvz' · intro hxu subst hxu left constructor · exact huv.symm · rintro ⟨z, hz, hvz, hzu⟩ rw [Sym2.eq_iff] at hz rcases hz with ⟨_, hxz⟩ | ⟨hvz', _⟩ · exfalso; exact hzu hxz.symm · exfalso; exact hvz.ne hvz' have hv1 : Nat.card ((gts_graph T u v u).neighborSet v) = 1 := by rw [hvset] rw [show Nat.card ({u} : Set V) = ({u} : Set V).ncard from by rw [← Set.ncard_univ, Set.ncard_coe]] simp have hv_not : ¬ (1 < Nat.card ((gts_graph T u v u).neighborSet v)) := by omega -- The beneficiary `u` keeps at least the neighbours `v` and one further old neighbour. have hu_nonleaf : 1 < Nat.card ((gts_graph T u v u).neighborSet u) := by have hcard : 1 < Fintype.card (T.neighborSet u) := by rw [← Nat.card_eq_fintype_card] omega obtain ⟨b, hb⟩ := Fintype.exists_ne_of_one_lt_card hcard ⟨v, (SimpleGraph.mem_neighborSet T u v).mpr huv⟩ have hwv : b.1 ≠ v := fun h => hb (Subtype.ext h) have hadjuv : (gts_graph T u v u).Adj u v := by rw [gts_graph, SimpleGraph.sup_adj] left rw [SimpleGraph.deleteEdges_adj] refine ⟨huv, ?_⟩ rintro ⟨z, hz, hvz, hzu⟩ rw [Sym2.eq_iff] at hz rcases hz with ⟨huv', _⟩ | ⟨huz, _⟩ · exact huv.ne huv' · exact hzu huz.symm have hadjuw : (gts_graph T u v u).Adj u b.1 := by rw [gts_graph, SimpleGraph.sup_adj] left rw [SimpleGraph.deleteEdges_adj] refine ⟨b.2, ?_⟩ rintro ⟨z, hz, hvz, hzu⟩ rw [Sym2.eq_iff] at hz rcases hz with ⟨huv', _⟩ | ⟨huz, hwv'⟩ · exact huv.ne huv' · exact hwv hwv' have hpos : 1 < ((gts_graph T u v u).neighborSet u).ncard := by rw [Set.one_lt_ncard] exact ⟨v, (SimpleGraph.mem_neighborSet _ _ _).mpr hadjuv, b.1, (SimpleGraph.mem_neighborSet _ _ _).mpr hadjuw, fun h => hwv h.symm⟩ have heq : Nat.card ((gts_graph T u v u).neighborSet u) = ((gts_graph T u v u).neighborSet u).ncard := by rw [← Set.ncard_univ, Set.ncard_coe] rw [heq] exact hpos -- Every vertex other than `v` has the same non-leaf status before and after. have hdegree : ∀ x : V, (x ≠ v → ((1 < Nat.card ((gts_graph T u v u).neighborSet x)) ↔ (1 < Nat.card (T.neighborSet x)))) := by intro x hxv by_cases hxu : x = u · subst hxu constructor · exact fun _ => hu · exact fun _ => hu_nonleaf · rw [op223_tree_adjacent_shift_other_degrees T u v hT huv x hxu hxv] -- Hence the old non-leaves are exactly `v` together with the new non-leaves. have hfilter : (Finset.univ.filter (fun x : V => 1 < Nat.card (T.neighborSet x))) = insert v (Finset.univ.filter (fun x : V => 1 < Nat.card ((gts_graph T u v u).neighborSet x))) := by ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert] constructor · intro hx by_cases hxv : x = v · exact Or.inl hxv · exact Or.inr ((hdegree x hxv).mpr hx) · intro hx rcases hx with hxv | hx · subst hxv omega · by_cases hxv : x = v · subst hxv omega · exact (hdegree x hxv).mp hx have hmem : v ∉ Finset.univ.filter (fun x : V => 1 < Nat.card ((gts_graph T u v u).neighborSet x)) := by simp only [Finset.mem_filter, Finset.mem_univ, true_and, not_lt] omega rw [hfilter] rw [Finset.card_insert_of_notMem hmem]