op223_slide_leaf_pendant_chain_is_tree
If v is a leaf of the tree X reached from u by a path p with all interior vertices of degree 2, and b is a neighbour of u outside p and not adjacent to v, then X − ub + vb is again a tree.
Statement
theorem op223_slide_leaf_pendant_chain_is_tree {V : Type*} [Fintype V] [DecidableEq V] (X : SimpleGraph V) (hX : X.IsTree) (u v b : V) (p : X.Walk u v) (huv : u ≠ v) (hp : p.IsPath) (hint : ∀ x ∈ p.support, x ≠ u → x ≠ v → Nat.card (X.neighborSet x) = 2) (hv : Nat.card (X.neighborSet v) = 1) (hub : X.Adj u b) (hvb : ¬ X.Adj v b) (hb : b ∉ p.support) : (X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).IsTree
- Source
- step towards op223_gts_poset_connectivity
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- Arena.Reachable.transReachability is transitive.
The proof, explained
The proof uses the characterization that a finite graph is a tree if and only if it is connected and has |V| - 1 edges. Removing the edge ub and adding vb preserves the edge count because ub was an edge of X and vb was not. Connectivity is maintained because the walk p connecting u and v does not contain b, so all its edges survive in X'; the removed edge ub is bypassed by traversing p from u to v and then taking the new edge vb.
The modified graph X' is defined by deleting edge ub and adding edge vb; from the fact that X is a tree, X is connected, |E(X)| + 1 = |V|, and V is nonempty.
We define X' as (X minus {ub}) union {vb}. Because X is a tree on a finite vertex set, the tree characterization implies that X is connected and its edge count plus 1 equals the number of vertices, which also ensures V is nonempty.
uses
SimpleGraph.isTree_iff_connected_and_card.mplet X' := X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)} have hX_conn : X.Connected := (SimpleGraph.isTree_iff_connected_and_card.mp hX).1 have hX_card : Nat.card ↑X.edgeSet + 1 = Nat.card V := (SimpleGraph.isTree_iff_connected_and_card.mp hX).2 have : Nonempty V := hX_conn.nonempty
v ≠ b.
If v = b, then b would be the end vertex of the walk p and therefore belong to the support of p, contradicting the hypothesis that b ∉ p.support.
have hvb_ne : v ≠ b := by rintro rfl exact hb p.end_mem_support
v and b are adjacent in X'.
X' contains the graph generated by the edge {vb}. Since v ≠ b, the pair {v, b} is not a self-loop, so v and b are adjacent in X'.
uses
SimpleGraph.sup_adj,SimpleGraph.fromEdgeSet_adjhave h_vb_adj : X'.Adj v b := by rw [SimpleGraph.sup_adj] right rw [SimpleGraph.fromEdgeSet_adj] exact ⟨rfl, hvb_ne⟩
Every edge of the walk p belongs to the edge set of X'.
Every edge of p is an edge in X. None of these edges can be {u, b}, because otherwise b would be in the support of p, contradicting b ∉ p.support. Thus every edge of p survives the removal of {u, b} and belongs to X'.
uses
SimpleGraph.edgeSet_sup,SimpleGraph.edgeSet_deleteEdges,Sym2.mem_mk_right,Set.mem_singleton_iff.mphave h_p_edges : ∀ e ∈ p.edges, e ∈ X'.edgeSet := by intro e he have he_in_X : e ∈ X.edgeSet := p.edges_subset_edgeSet he have he_ne : e ≠ s(u, b) := by rintro rfl have : b ∈ p.support := p.mem_support_of_mem_edges he (Sym2.mem_mk_right u b) exact hb this rw [SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges] left exact ⟨he_in_X, fun h => he_ne (Set.mem_singleton_iff.mp h)⟩
u can reach v, and u can reach b in X'.
Since all edges of p are present in X', the walk p transfers to a walk from u to v in X'. Concatenating this walk with the edge vb gives reachability from u to b in X'.
have h_uv_reach : X'.Reachable u v := ⟨p.transfer X' h_p_edges⟩ have h_ub_reach : X'.Reachable u b := h_uv_reach.trans h_vb_adj.reachable
Every pair of adjacent vertices in X is reachable from each other in X'.
Consider any adjacent vertices x, y in X. If {x, y} is the deleted edge {u, b}, they are reachable via the path from u to b in X'. If {x, y} is not {u, b}, the edge was not deleted, so x and y remain adjacent and thus reachable in X'.
uses
Sym2.eq_iff,SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adj,Set.mem_singleton_iff.mphave h_reach : ∀ ⦃x y : V⦄, X.Adj x y → X'.Reachable x y := by intro x y hxy by_cases h : s(x, y) = s(u, b) · rw [Sym2.eq_iff] at h rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h_ub_reach · exact h_ub_reach.symm · have : X'.Adj x y := by rw [SimpleGraph.sup_adj] left rw [SimpleGraph.deleteEdges_adj] exact ⟨hxy, fun h' => h (Set.mem_singleton_iff.mp h')⟩ exact this.reachable
X' is connected.
Since X is connected, any two vertices x, y have a walk in X between them. By induction on this walk, replacing each step in X with reachability of its endpoints in X', x can reach y in X'. Since V is nonempty, X' is connected.
uses
SimpleGraph.Reachable.reflhave h_preconn : X'.Preconnected := by intro x y obtain ⟨w⟩ := hX_conn.preconnected x y induction w with | nil => exact SimpleGraph.Reachable.refl _ | cons hadj _ ih => exact (h_reach hadj).trans ih have h_conn : X'.Connected := ⟨h_preconn⟩
The edge set of X' is (E(X) \ {ub}) ∪ {vb}.
By definition, X' is formed by deleting {ub} from X and adjoining the edge set {vb}. Since v ≠ b, the pair {v, b} is not on the diagonal, so the graph induced by {vb} has edge set precisely {vb}.
uses
SimpleGraph.edgeSet_sup,SimpleGraph.edgeSet_deleteEdges,SimpleGraph.edgeSet_fromEdgeSet,sdiff_eq_self_iff_disjoint,Set.disjoint_singleton_right,Sym2.mem_diagSet,Sym2.mk_isDiag_iffhave h_edgeSet : X'.edgeSet = (X.edgeSet \ {s(u, b)}) ∪ {s(v, b)} := by dsimp [X'] rw [SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges, SimpleGraph.edgeSet_fromEdgeSet] have : ({s(v, b)} : Set (Sym2 V)) \ Sym2.diagSet = {s(v, b)} := by rw [sdiff_eq_self_iff_disjoint] rw [Set.disjoint_singleton_right] rw [Sym2.mem_diagSet, Sym2.mk_isDiag_iff] exact hvb_ne rw [this]
The edge set of X' has the same cardinality as that of X.
The edge ub is in X, while vb is not in X by assumption. Therefore, removing {ub} decreases the edge count by 1, and inserting {vb} increases it by 1, leaving the total number of edges unchanged.
uses
SimpleGraph.mem_edgeSet,Set.union_singleton,Set.ncard_insert_of_notMem,Set.ncard_sdiff_singleton_add_onehave ha : s(u, b) ∈ X.edgeSet := (SimpleGraph.mem_edgeSet X).mpr hub have h_not : s(v, b) ∉ X.edgeSet := mt (SimpleGraph.mem_edgeSet X).mp hvb have h_ncard : ((X.edgeSet \ {s(u, b)}) ∪ {s(v, b)}).ncard = X.edgeSet.ncard := by have : (X.edgeSet \ {s(u, b)}) ∪ {s(v, b)} = insert s(v, b) (X.edgeSet \ {s(u, b)}) := by exact Set.union_singleton rw [this] have hb' : s(v, b) ∉ X.edgeSet \ {s(u, b)} := fun h => h_not h.1 rw [Set.ncard_insert_of_notMem hb'] have := Set.ncard_sdiff_singleton_add_one ha omega
|E(X')| + 1 = |V|, and therefore X' is a tree.
Since |E(X')| = |E(X)|, we have |E(X')| + 1 = |V|. A finite connected graph with |V| - 1 edges is a tree, completing the proof.
uses
Nat.card_coe_set_eq,SimpleGraph.isTree_iff_connected_and_card.mprhave h_card : Nat.card ↑X'.edgeSet + 1 = Nat.card V := by rw [Nat.card_coe_set_eq, h_edgeSet, h_ncard, ← Nat.card_coe_set_eq] exact hX_card exact SimpleGraph.isTree_iff_connected_and_card.mpr ⟨h_conn, h_card⟩
Nat.card_coe_set_eq- The cardinality of a set coerced to a type equals its set cardinality (`ncard`).
Set.mem_singleton_iff.mp- If an element is in the singleton set {b}, then it equals b.
Set.disjoint_singleton_right- A set is disjoint from a singleton {a} if and only if a is not in the set.
Set.ncard_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
Set.ncard_sdiff_singleton_add_one- Removing an element that belongs to a finite set decreases its cardinality by 1.
Set.union_singleton- The union of a set s with {a} equals inserting a into s.
SimpleGraph.deleteEdges_adj- Two vertices are adjacent after deleting a set of edges if and only if they were adjacent originally and the edge between them was not deleted.
SimpleGraph.edgeSet_deleteEdges- The edge set of a graph with deleted edges is the original edge set minus the deleted set.
SimpleGraph.edgeSet_fromEdgeSet- The edge set of the graph built from a set of pairs is that set minus the diagonal pairs (self-loops).
SimpleGraph.edgeSet_sup- The edge set of the union of two graphs is the union of their edge sets.
SimpleGraph.fromEdgeSet_adj- In the graph constructed from a set of pairs, two distinct vertices are adjacent if and only if their connecting pair belongs to the set.
SimpleGraph.isTree_iff_connected_and_card.mp- A tree on a finite vertex set is connected and satisfies |E| + 1 = |V|.
SimpleGraph.isTree_iff_connected_and_card.mpr- A graph on a finite vertex set that is connected and satisfies |E| + 1 = |V| is a tree.
SimpleGraph.mem_edgeSet- An unordered pair belongs to the edge set of a graph if and only if its endpoints are adjacent.
SimpleGraph.Reachable.refl- Every vertex is reachable from itself.
SimpleGraph.sup_adj- In the union of two graphs, two vertices are adjacent if and only if they are adjacent in at least one of the graphs.
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) ∨ (x = w ∧ y = z).
Sym2.mem_diagSet- An unordered pair is in the diagonal set if and only if it is diagonal.
Sym2.mem_mk_right- The second element y is a member of the unordered pair s(x, y).
Sym2.mk_isDiag_iff- An unordered pair s(x, y) is diagonal if and only if x = y.
sdiff_eq_self_iff_disjoint- Set difference x \ y equals x if and only if y and x are disjoint.
- The hypotheses `hint` (that interior vertices of p have degree 2) and `hv` (that v is a leaf) are not used anywhere in the formal proof: any edge slide along a path avoiding the displaced endpoint b preserves connectivity and edge count, which suffices to establish that the result is a tree.
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.
/-- The single-edge leaf slide along a pendant chain preserves being a tree. -/theorem op223_slide_leaf_pendant_chain_is_tree {V : Type*} [Fintype V] [DecidableEq V] (X : SimpleGraph V) (hX : X.IsTree) (u v b : V) (p : X.Walk u v) (huv : u ≠ v) (hp : p.IsPath) (hint : ∀ x ∈ p.support, x ≠ u → x ≠ v → Nat.card (X.neighborSet x) = 2) (hv : Nat.card (X.neighborSet v) = 1) (hub : X.Adj u b) (hvb : ¬ X.Adj v b) (hb : b ∉ p.support) : (X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}).IsTree := by let X' := X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)} have hX_conn : X.Connected := (SimpleGraph.isTree_iff_connected_and_card.mp hX).1 have hX_card : Nat.card ↑X.edgeSet + 1 = Nat.card V := (SimpleGraph.isTree_iff_connected_and_card.mp hX).2 have : Nonempty V := hX_conn.nonempty have hvb_ne : v ≠ b := by rintro rfl exact hb p.end_mem_support have h_vb_adj : X'.Adj v b := by rw [SimpleGraph.sup_adj] right rw [SimpleGraph.fromEdgeSet_adj] exact ⟨rfl, hvb_ne⟩ have h_p_edges : ∀ e ∈ p.edges, e ∈ X'.edgeSet := by intro e he have he_in_X : e ∈ X.edgeSet := p.edges_subset_edgeSet he have he_ne : e ≠ s(u, b) := by rintro rfl have : b ∈ p.support := p.mem_support_of_mem_edges he (Sym2.mem_mk_right u b) exact hb this rw [SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges] left exact ⟨he_in_X, fun h => he_ne (Set.mem_singleton_iff.mp h)⟩ have h_uv_reach : X'.Reachable u v := ⟨p.transfer X' h_p_edges⟩ have h_ub_reach : X'.Reachable u b := h_uv_reach.trans h_vb_adj.reachable have h_reach : ∀ ⦃x y : V⦄, X.Adj x y → X'.Reachable x y := by intro x y hxy by_cases h : s(x, y) = s(u, b) · rw [Sym2.eq_iff] at h rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact h_ub_reach · exact h_ub_reach.symm · have : X'.Adj x y := by rw [SimpleGraph.sup_adj] left rw [SimpleGraph.deleteEdges_adj] exact ⟨hxy, fun h' => h (Set.mem_singleton_iff.mp h')⟩ exact this.reachable have h_preconn : X'.Preconnected := by intro x y obtain ⟨w⟩ := hX_conn.preconnected x y induction w with | nil => exact SimpleGraph.Reachable.refl _ | cons hadj _ ih => exact (h_reach hadj).trans ih have h_conn : X'.Connected := ⟨h_preconn⟩ have h_edgeSet : X'.edgeSet = (X.edgeSet \ {s(u, b)}) ∪ {s(v, b)} := by dsimp [X'] rw [SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges, SimpleGraph.edgeSet_fromEdgeSet] have : ({s(v, b)} : Set (Sym2 V)) \ Sym2.diagSet = {s(v, b)} := by rw [sdiff_eq_self_iff_disjoint] rw [Set.disjoint_singleton_right] rw [Sym2.mem_diagSet, Sym2.mk_isDiag_iff] exact hvb_ne rw [this] have ha : s(u, b) ∈ X.edgeSet := (SimpleGraph.mem_edgeSet X).mpr hub have h_not : s(v, b) ∉ X.edgeSet := mt (SimpleGraph.mem_edgeSet X).mp hvb have h_ncard : ((X.edgeSet \ {s(u, b)}) ∪ {s(v, b)}).ncard = X.edgeSet.ncard := by have : (X.edgeSet \ {s(u, b)}) ∪ {s(v, b)} = insert s(v, b) (X.edgeSet \ {s(u, b)}) := by exact Set.union_singleton rw [this] have hb' : s(v, b) ∉ X.edgeSet \ {s(u, b)} := fun h => h_not h.1 rw [Set.ncard_insert_of_notMem hb'] have := Set.ncard_sdiff_singleton_add_one ha omega have h_card : Nat.card ↑X'.edgeSet + 1 = Nat.card V := by rw [Nat.card_coe_set_eq, h_edgeSet, h_ncard, ← Nat.card_coe_set_eq] exact hX_card exact SimpleGraph.isTree_iff_connected_and_card.mpr ⟨h_conn, h_card⟩