AFTD Auto-Formalizing Theoretical Domains

op223_tree_adjacent_shift_nonleaf_count

theoremverified

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

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.

  1. 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.

    lines 2–27

    uses SimpleGraph.mem_neighborSet, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Set.mem_ofPred_eq, Set.mem_singleton_iff, Sym2.eq_iff

      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'
  2. 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.

    lines 28–33

    uses Set.ncard_univ, Set.ncard_coe

      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
  3. 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.

    lines 35–70

    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_coe

      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
  4. 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.

    lines 72–80

    uses op223_tree_adjacent_shift_other_degrees

      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]
  5. 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.

    lines 82–98

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Or.inl, Or.inr

      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
  6. 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.

    lines 99–103

    uses Finset.mem_filter, Finset.mem_univ, true_and, not_lt, Finset.card_insert_of_notMem

      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]
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.

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

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]
See it in the graphDiscuss this resultChallenge it