AFTD Auto-Formalizing Theoretical Domains

op223_leaf_slide_count_with_source_degree

theoremverified

If a leaf v gains an edge to b while an edge from b to a vertex u of degree at least three is removed, with distinct u and v and no previous v-b edge, the number of leaves drops by exactly one.

Statement

theorem op223_leaf_slide_count_with_source_degree {V : Type*} [Fintype V] [DecidableEq V] (X : SimpleGraph V) (u v b : V) (huv : u ≠ v) (hbv : b ≠ v) (hub : X.Adj u b) (hvb : ¬ X.Adj v b) (hu : 3 ≤ Nat.card (X.neighborSet u)) (hv : Nat.card (X.neighborSet v) = 1) : (Finset.univ.filter (fun x : V => Nat.card ((X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet x) = 1)).card + 1 = (Finset.univ.filter (fun x : V => Nat.card (X.neighborSet x) = 1)).card
Source
arXiv:2610.17078 Open Problem 6.1; corrected auxiliary statement, experiment 23205
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof analyzes how neighbor sets and degrees change when an edge ub (with deg(u) ≥ 3) is replaced by vb (with v a leaf and not adjacent to b). Helper lemmas determine the new neighborhoods: v gains b, u loses b, b swaps u for v, and all other vertices are unaffected. Consequently, the degree of b is unchanged, u retains degree at least 2, and v increases its degree from 1 to 2, ceasing to be a leaf. Therefore, the set of leaves of X is precisely the set of leaves of the modified graph with v added, so the leaf count decreases by exactly one.

  1. In a graph consisting of a single edge {x, y} with x ≠ y, the neighbor set of z is {y} if z = x, {x} if z = y, and ∅ otherwise. automation

    By extensionality, a vertex w is adjacent to z if and only if the edge s(z, w) equals s(x, y) with z ≠ w. Splitting on whether z = x or z = y yields the three cases.

    lines 5–7

    uses SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Set.mem_singleton_iff, Sym2.eq_iff

      ext w
      simp only [SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Set.mem_singleton_iff, Sym2.eq_iff]
      split_ifs with h1 h2 <;> aesop
  2. For any vertex x, the neighbor set in (X \ {ub}) ∪ {vb} is (N_X(x) \ N_{ub}(x)) ∪ N_{vb}(x).

    Graph edge deletion is set difference and edge addition is graph supremum; neighbor sets distribute over both operations.

    lines 14–15

    uses SimpleGraph.neighborSet_sup, SimpleGraph.neighborSet_sdiff

      change ((X \ SimpleGraph.fromEdgeSet {s(u, b)}) ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet x = _
      rw [SimpleGraph.neighborSet_sup, SimpleGraph.neighborSet_sdiff]
  3. In the modified graph, the neighbor set of u is N_X(u) \ {b}.

    Applying the general slide formula at u, the deleted edge {u, b} removes b, while the added edge {v, b} contains neither endpoint equal to u since u ≠ v and u ≠ b.

    lines 22–27

    uses op223_leaf_slide_count_with_source_degree_neighborSet_slide, op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton

      have hub_ne : u ≠ b := X.ne_of_adj hub
      have hvb_ne : v ≠ b := hbv.symm
      rw [op223_leaf_slide_count_with_source_degree_neighborSet_slide,
          op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton u b u hub_ne,
          op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton v b u hvb_ne]
      simp [huv, hub_ne]
  4. In the modified graph, the neighbor set of v is N_X(v) ∪ {b}.

    Applying the slide formula at v, the deleted edge {u, b} does not contain v (as v ≠ u and v ≠ b), while the added edge {v, b} adds neighbor b.

    lines 34–39

    uses op223_leaf_slide_count_with_source_degree_neighborSet_slide, op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton

      have hub_ne : u ≠ b := X.ne_of_adj hub
      have hvb_ne : v ≠ b := hbv.symm
      rw [op223_leaf_slide_count_with_source_degree_neighborSet_slide,
          op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton u b v hub_ne,
          op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton v b v hvb_ne]
      simp [huv.symm, hbv.symm]
  5. In the modified graph, the neighbor set of b is (N_X(b) \ {u}) ∪ {v}.

    Applying the slide formula at b, {u, b} contributes {u} to be removed and {v, b} contributes {v} to be added.

    lines 46–51

    uses op223_leaf_slide_count_with_source_degree_neighborSet_slide, op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton

      have hub_ne : u ≠ b := X.ne_of_adj hub
      have hvb_ne : v ≠ b := hbv.symm
      rw [op223_leaf_slide_count_with_source_degree_neighborSet_slide,
          op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton u b b hub_ne,
          op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton v b b hvb_ne]
      simp [hub_ne.symm, hbv]
  6. Any vertex x distinct from u, v, and b has its neighbor set unchanged: N_{X'}(x) = N_X(x).

    Since x is not an endpoint of either the removed edge {u, b} or the added edge {v, b}, both single-edge neighbor sets at x are empty.

    lines 58–63

    uses op223_leaf_slide_count_with_source_degree_neighborSet_slide, op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton

      have hub_ne : u ≠ b := X.ne_of_adj hub
      have hvb_ne : v ≠ b := hbv.symm
      rw [op223_leaf_slide_count_with_source_degree_neighborSet_slide,
          op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton u b x hub_ne,
          op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton v b x hvb_ne]
      simp [hxu, hxb, hxv]
  7. Define the modified graph X', the leaf sets s (of X') and t (of X), and instantiate the neighbor set equations for v, u, and b.

    We introduce X' for the graph after the leaf slide, s and t for the sets of degree-1 vertices in X' and X, and invoke the helper lemmas to record the updated neighborhoods of v, u, and b.

    lines 66–74

    uses op223_leaf_slide_count_with_source_degree_neighborSet_slide_v, op223_leaf_slide_count_with_source_degree_neighborSet_slide_u, op223_leaf_slide_count_with_source_degree_neighborSet_slide_b

      let X' := X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}
      let s := Finset.univ.filter (fun x : V => Nat.card (X'.neighborSet x) = 1)
      let t := Finset.univ.filter (fun x : V => Nat.card (X.neighborSet x) = 1)
      have h_nv : X'.neighborSet v = X.neighborSet v ∪ {b} :=
        op223_leaf_slide_count_with_source_degree_neighborSet_slide_v X u v b huv hbv hub
      have h_nu : X'.neighborSet u = X.neighborSet u \ {b} :=
        op223_leaf_slide_count_with_source_degree_neighborSet_slide_u X u v b huv hbv hub
      have h_nb : X'.neighborSet b = (X.neighborSet b \ {u}) ∪ {v} :=
        op223_leaf_slide_count_with_source_degree_neighborSet_slide_b X u v b hbv hub
  8. In X', the degree of v is 2.

    The neighborhood of v in X' is N_X(v) ∪ {b}. Because v was not adjacent to b in X, inserting b increases its cardinality from 1 to 2.

    lines 75–78

    uses Nat.card_coe_set_eq, Set.union_singleton, Set.ncard_insert_of_notMem

      have card_v : Nat.card (X'.neighborSet v) = 2 := by
        rw [Nat.card_coe_set_eq, h_nv, Set.union_singleton]
        have hb : b ∉ X.neighborSet v := hvb
        rw [Set.ncard_insert_of_notMem hb, ← Nat.card_coe_set_eq, hv]
  9. v is a leaf of X but not of X' (v ∈ t and v ∉ s). automation

    Since deg_{X'}(v) = 2 ≠ 1, v does not satisfy the membership condition for s. Since deg_X(v) = 1, v satisfies the condition for t.

    lines 79–84

    uses Finset.mem_filter, Finset.mem_univ, true_and

      have hv_s : v ∉ s := by
        simp only [s, Finset.mem_filter, Finset.mem_univ, true_and]
        rw [card_v]
        decide
      have hv_t : v ∈ t := by
        simp only [t, Finset.mem_filter, Finset.mem_univ, true_and, hv]
  10. u is not a leaf in X' (deg_{X'}(u) ≠ 1). automation

    Removing neighbor b from N_X(u) reduces its cardinality by 1. Since |N_X(u)| ≥ 3, the resulting cardinality is at least 2, which is not 1.

    lines 85–90

    uses Nat.card_coe_set_eq, Set.ncard_sdiff_singleton_add_one

      have card_u : Nat.card (X'.neighborSet u) ≠ 1 := by
        rw [Nat.card_coe_set_eq, h_nu]
        have hb : b ∈ X.neighborSet u := hub
        have h_diff := Set.ncard_sdiff_singleton_add_one hb
        rw [Nat.card_coe_set_eq] at hu
        omega
  11. The degree of b is preserved: |N_{X'}(b)| = |N_X(b)|. automation

    In X', neighbor u is removed and non-neighbor v is inserted, so the cardinality decreases by 1 and then increases by 1, leaving the total unchanged.

    lines 91–98

    uses Nat.card_coe_set_eq, Set.union_singleton, Set.ncard_insert_of_notMem, Set.ncard_sdiff_singleton_add_one

      have card_b : Nat.card (X'.neighborSet b) = Nat.card (X.neighborSet b) := by
        rw [Nat.card_coe_set_eq, h_nb, Set.union_singleton]
        have hu_mem : u ∈ X.neighborSet b := hub.symm
        have hv_not : v ∉ X.neighborSet b \ {u} := fun h => hvb (h.1 : X.Adj b v).symm
        rw [Set.ncard_insert_of_notMem hv_not]
        have h_diff := Set.ncard_sdiff_singleton_add_one hu_mem
        rw [Nat.card_coe_set_eq]
        omega
  12. Every vertex x ≠ v is a leaf in X' if and only if it is a leaf in X (x ∈ s ↔ x ∈ t).

    For x = u, neither degree is 1 (deg_X(u) ≥ 3 and deg_{X'}(u) ≠ 1). For x = b, the degrees in X and X' are equal. For any other vertex, the neighborhood is completely unchanged.

    lines 99–111

    uses Finset.mem_filter, Finset.mem_univ, true_and, op223_leaf_slide_count_with_source_degree_neighborSet_slide_other

      have h_iff : ∀ x ≠ v, x ∈ s ↔ x ∈ t := by
        intro x hx
        simp only [s, t, Finset.mem_filter, Finset.mem_univ, true_and]
        by_cases hxu : x = u
        · subst hxu
          constructor
          · intro h1; exact (card_u h1).elim
          · intro h2; omega
        · by_cases hxb : x = b
          · subst hxb
            rw [card_b]
          · have h_oth := op223_leaf_slide_count_with_source_degree_neighborSet_slide_other X u v b hbv hub hxu hx hxb
            rw [h_oth]
  13. The leaf set of X is obtained by adding v to the leaf set of X': t = insert v s.

    By extensionality, for x = v we have v ∈ t and v ∈ insert v s; for x ≠ v, membership in t is equivalent to membership in s, hence in insert v s.

    lines 112–117

      have ht : t = insert v s := by
        ext x
        by_cases hx : x = v
        · subst hx
          simp [hv_t]
        · simp [hx, (h_iff x hx).symm]
  14. The number of leaves in X' plus 1 equals the number of leaves in X (|s| + 1 = |t|).

    Since t = insert v s and v ∉ s, the cardinality of t is |s| + 1.

    lines 118–119

    uses Finset.card_insert_of_notMem

      change s.card + 1 = t.card
      rw [ht, Finset.card_insert_of_notMem hv_s]
SimpleGraph.mem_neighborSet
A vertex w belongs to the neighbor set of v in G if and only if v and w are adjacent in G.
SimpleGraph.fromEdgeSet_adj
In a graph built from a set of undirected edges s, vertices v and w are adjacent if and only if the edge s(v, w) belongs to s and v ≠ w.
Set.mem_singleton_iff
An element a belongs to the singleton {b} if and only if a = b.
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).
SimpleGraph.neighborSet_sup
The neighbor set of a vertex in the union (supremum) of two graphs is the union of its neighbor sets in each graph.
SimpleGraph.neighborSet_sdiff
The neighbor set of a vertex in the difference of two graphs is the set difference of its neighbor sets.
op223_leaf_slide_count_with_source_degree_neighborSet_slide
In the graph obtained by removing edge {u, b} and adding edge {v, b}, the neighbor set of x is (N_X(x) \ N_{ub}(x)) ∪ N_{vb}(x).
op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton
In the single-edge graph with edge {x, y} for distinct x and y, the neighbor set of z is {y} if z = x, {x} if z = y, and empty otherwise.
op223_leaf_slide_count_with_source_degree_neighborSet_slide_v
When replacing edge {u, b} with {v, b}, the neighbor set of v becomes N_X(v) ∪ {b}.
op223_leaf_slide_count_with_source_degree_neighborSet_slide_u
When replacing edge {u, b} with {v, b}, the neighbor set of u becomes N_X(u) \ {b}.
op223_leaf_slide_count_with_source_degree_neighborSet_slide_b
When replacing edge {u, b} with {v, b}, the neighbor set of b becomes (N_X(b) \ {u}) ∪ {v}.
Nat.card_coe_set_eq
The cardinality Nat.card of a set coerced to a subtype equals its set cardinality Set.ncard.
Set.union_singleton
The union of a set s with a singleton {a} is the set insert a s.
Set.ncard_insert_of_notMem
Inserting an element not in a finite set increases its cardinality by 1.
Finset.mem_filter
An element is in Finset.filter p s if and only if it is in s and satisfies predicate p.
Finset.mem_univ
Every element of a finite type belongs to Finset.univ.
true_and
The conjunction of True and p simplifies to p.
Set.ncard_sdiff_singleton_add_one
Removing an element from a finite set containing it yields a set whose cardinality plus 1 equals the original cardinality.
op223_leaf_slide_count_with_source_degree_neighborSet_slide_other
When replacing edge {u, b} with {v, b}, any vertex other than u, v, and b has its neighbor set unchanged.
Finset.card_insert_of_notMem
Inserting an element not already in a finite set yields a finset whose cardinality is 1 greater.

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

lemma op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton    {V : Type*} [DecidableEq V] (x y z : V) (h : x ≠ y) :    (SimpleGraph.fromEdgeSet {s(x, y)}).neighborSet z =      if z = x then {y} else if z = y then {x} else ∅ := by  ext w  simp only [SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Set.mem_singleton_iff, Sym2.eq_iff]  split_ifs with h1 h2 <;> aesoplemma op223_leaf_slide_count_with_source_degree_neighborSet_slide    {V : Type*} (X : SimpleGraph V) (u v b x : V) :    (X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet x =      (X.neighborSet x \ (SimpleGraph.fromEdgeSet {s(u, b)}).neighborSet x) ∪        (SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet x := by  change ((X \ SimpleGraph.fromEdgeSet {s(u, b)}) ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet x = _  rw [SimpleGraph.neighborSet_sup, SimpleGraph.neighborSet_sdiff]lemma op223_leaf_slide_count_with_source_degree_neighborSet_slide_u    {V : Type*} [DecidableEq V] (X : SimpleGraph V) (u v b : V)    (huv : u ≠ v) (hbv : b ≠ v) (hub : X.Adj u b) :    (X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet u =      X.neighborSet u \ {b} := by  have hub_ne : u ≠ b := X.ne_of_adj hub  have hvb_ne : v ≠ b := hbv.symm  rw [op223_leaf_slide_count_with_source_degree_neighborSet_slide,      op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton u b u hub_ne,      op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton v b u hvb_ne]  simp [huv, hub_ne]lemma op223_leaf_slide_count_with_source_degree_neighborSet_slide_v    {V : Type*} [DecidableEq V] (X : SimpleGraph V) (u v b : V)    (huv : u ≠ v) (hbv : b ≠ v) (hub : X.Adj u b) :    (X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet v =      X.neighborSet v ∪ {b} := by  have hub_ne : u ≠ b := X.ne_of_adj hub  have hvb_ne : v ≠ b := hbv.symm  rw [op223_leaf_slide_count_with_source_degree_neighborSet_slide,      op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton u b v hub_ne,      op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton v b v hvb_ne]  simp [huv.symm, hbv.symm]lemma op223_leaf_slide_count_with_source_degree_neighborSet_slide_b    {V : Type*} [DecidableEq V] (X : SimpleGraph V) (u v b : V)    (hbv : b ≠ v) (hub : X.Adj u b) :    (X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet b =      (X.neighborSet b \ {u}) ∪ {v} := by  have hub_ne : u ≠ b := X.ne_of_adj hub  have hvb_ne : v ≠ b := hbv.symm  rw [op223_leaf_slide_count_with_source_degree_neighborSet_slide,      op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton u b b hub_ne,      op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton v b b hvb_ne]  simp [hub_ne.symm, hbv]lemma op223_leaf_slide_count_with_source_degree_neighborSet_slide_other    {V : Type*} [DecidableEq V] (X : SimpleGraph V) (u v b : V)    (hbv : b ≠ v) (hub : X.Adj u b) {x : V} (hxu : x ≠ u) (hxv : x ≠ v) (hxb : x ≠ b) :    (X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet x =      X.neighborSet x := by  have hub_ne : u ≠ b := X.ne_of_adj hub  have hvb_ne : v ≠ b := hbv.symm  rw [op223_leaf_slide_count_with_source_degree_neighborSet_slide,      op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton u b x hub_ne,      op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singleton v b x hvb_ne]  simp [hxu, hxb, hxv]theorem op223_leaf_slide_count_with_source_degree {V : Type*} [Fintype V] [DecidableEq V] (X : SimpleGraph V) (u v b : V) (huv : u ≠ v) (hbv : b ≠ v) (hub : X.Adj u b) (hvb : ¬ X.Adj v b) (hu : 3 ≤ Nat.card (X.neighborSet u)) (hv : Nat.card (X.neighborSet v) = 1) : (Finset.univ.filter (fun x : V => Nat.card ((X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet x) = 1)).card + 1 = (Finset.univ.filter (fun x : V => Nat.card (X.neighborSet x) = 1)).card := by  let X' := X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}  let s := Finset.univ.filter (fun x : V => Nat.card (X'.neighborSet x) = 1)  let t := Finset.univ.filter (fun x : V => Nat.card (X.neighborSet x) = 1)  have h_nv : X'.neighborSet v = X.neighborSet v ∪ {b} :=    op223_leaf_slide_count_with_source_degree_neighborSet_slide_v X u v b huv hbv hub  have h_nu : X'.neighborSet u = X.neighborSet u \ {b} :=    op223_leaf_slide_count_with_source_degree_neighborSet_slide_u X u v b huv hbv hub  have h_nb : X'.neighborSet b = (X.neighborSet b \ {u}) ∪ {v} :=    op223_leaf_slide_count_with_source_degree_neighborSet_slide_b X u v b hbv hub  have card_v : Nat.card (X'.neighborSet v) = 2 := by    rw [Nat.card_coe_set_eq, h_nv, Set.union_singleton]    have hb : b ∉ X.neighborSet v := hvb    rw [Set.ncard_insert_of_notMem hb, ← Nat.card_coe_set_eq, hv]  have hv_s : v ∉ s := by    simp only [s, Finset.mem_filter, Finset.mem_univ, true_and]    rw [card_v]    decide  have hv_t : v ∈ t := by    simp only [t, Finset.mem_filter, Finset.mem_univ, true_and, hv]  have card_u : Nat.card (X'.neighborSet u) ≠ 1 := by    rw [Nat.card_coe_set_eq, h_nu]    have hb : b ∈ X.neighborSet u := hub    have h_diff := Set.ncard_sdiff_singleton_add_one hb    rw [Nat.card_coe_set_eq] at hu    omega  have card_b : Nat.card (X'.neighborSet b) = Nat.card (X.neighborSet b) := by    rw [Nat.card_coe_set_eq, h_nb, Set.union_singleton]    have hu_mem : u ∈ X.neighborSet b := hub.symm    have hv_not : v ∉ X.neighborSet b \ {u} := fun h => hvb (h.1 : X.Adj b v).symm    rw [Set.ncard_insert_of_notMem hv_not]    have h_diff := Set.ncard_sdiff_singleton_add_one hu_mem    rw [Nat.card_coe_set_eq]    omega  have h_iff : ∀ x ≠ v, x ∈ s ↔ x ∈ t := by    intro x hx    simp only [s, t, Finset.mem_filter, Finset.mem_univ, true_and]    by_cases hxu : x = u    · subst hxu      constructor      · intro h1; exact (card_u h1).elim      · intro h2; omega    · by_cases hxb : x = b      · subst hxb        rw [card_b]      · have h_oth := op223_leaf_slide_count_with_source_degree_neighborSet_slide_other X u v b hbv hub hxu hx hxb        rw [h_oth]  have ht : t = insert v s := by    ext x    by_cases hx : x = v    · subst hx      simp [hv_t]    · simp [hx, (h_iff x hx).symm]  change s.card + 1 = t.card  rw [ht, Finset.card_insert_of_notMem hv_s]
See it in the graphDiscuss this resultChallenge it