op223_leaf_slide_count_with_source_degree
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.
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.
uses
SimpleGraph.mem_neighborSet,SimpleGraph.fromEdgeSet_adj,Set.mem_singleton_iff,Sym2.eq_iffext w simp only [SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Set.mem_singleton_iff, Sym2.eq_iff] split_ifs with h1 h2 <;> aesop
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.
uses
SimpleGraph.neighborSet_sup,SimpleGraph.neighborSet_sdiffchange ((X \ SimpleGraph.fromEdgeSet {s(u, b)}) ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).neighborSet x = _ rw [SimpleGraph.neighborSet_sup, SimpleGraph.neighborSet_sdiff]
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.
uses
op223_leaf_slide_count_with_source_degree_neighborSet_slide,op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singletonhave 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]
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.
uses
op223_leaf_slide_count_with_source_degree_neighborSet_slide,op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singletonhave 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]
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.
uses
op223_leaf_slide_count_with_source_degree_neighborSet_slide,op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singletonhave 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]
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.
uses
op223_leaf_slide_count_with_source_degree_neighborSet_slide,op223_leaf_slide_count_with_source_degree_neighborSet_fromEdgeSet_singletonhave 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]
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.
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_blet 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
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.
uses
Nat.card_coe_set_eq,Set.union_singleton,Set.ncard_insert_of_notMemhave 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]
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.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave 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]
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.
uses
Nat.card_coe_set_eq,Set.ncard_sdiff_singleton_add_onehave 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
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.
uses
Nat.card_coe_set_eq,Set.union_singleton,Set.ncard_insert_of_notMem,Set.ncard_sdiff_singleton_add_onehave 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
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.
uses
Finset.mem_filter,Finset.mem_univ,true_and,op223_leaf_slide_count_with_source_degree_neighborSet_slide_otherhave 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]
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.
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]
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.
uses
Finset.card_insert_of_notMemchange 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.
- The proof frequently bridges type-theoretic cardinality `Nat.card` and set cardinality `Set.ncard` using `Nat.card_coe_set_eq`.
- The arithmetic on degree counts and leaf bounds in steps 9, 10, and 11 is discharged by automated tactics (`decide` and `omega`).
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.
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]