tree_delete_edge_reconnect_isTree
Let T be a tree on a finite vertex type V, and let vw be an edge of T. If u is a vertex not incident to vw (u ≠ v and u ≠ w), then there exists x ∈ {v, w} such that the graph obtained by deleting edge vw and adding edge ux is a tree.
Statement
theorem tree_delete_edge_reconnect_isTree {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (hT : T.IsTree) (u v w : V) (he : T.Adj v w) (huv : u ≠ v) (huw : u ≠ w) : ∃ x : V, (x = v ∨ x = w) ∧ (T.deleteEdges {s(v, w)} ⊔ SimpleGraph.fromEdgeSet {s(u, x)}).IsTree
- Source
- arXiv:2610.17078 Lemma 3.1 proof
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_tree_iff_is_acyclic_and_cardA simple graph G on a finite vertex type V is a tree if and only if G is acyclic and the number of edges plus 1 equals the number of…
- Arena.Reachable.transReachability is transitive.
Read back from the Lean
For any finite type V with decidable equality, any simple graph T on V that is a tree, and any vertices u, v, w ∈ V such that v and w are adjacent in T, u ≠ v, and u ≠ w: there exists a vertex x ∈ V such that (x = v ∨ x = w) and the graph obtained from T by deleting the edge s(v, w) and taking the graph union with the single edge s(u, x) (i.e. T.deleteEdges {s(v, w)} ⊔ SimpleGraph.fromEdgeSet {s(u, x)}) is a tree.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Since T is a tree, deleting the edge vw disconnects T into two components, one containing v and the other w. Because u is distinct from both endpoints, it belongs to one of these components, allowing us to choose x ∈ {v, w} to be the endpoint in the opposite component. Adding the edge ux reconnects the two components through u, ensuring that every edge of T is reachable in the new graph, which makes the new graph connected. Finally, since ux was not already an edge of the edge-deleted graph, removing vw and adding ux preserves the total number of edges, so the new graph has |V| - 1 edges and is connected, hence it is a tree.
Reachability in G implies reachability in G', provided that every adjacent pair in G is reachable in G'.
We induct on the walk p between x and y in G. If the walk is empty (nil), x = y, and reachability in G' is reflexive via `SimpleGraph.Reachable.rfl`. In the inductive step (cons), the walk begins with an edge between u and v followed by a tail walk from v to w. By hypothesis h, u and v are reachable in G', and by the induction hypothesis, v and w are reachable in G'. Composing these two reachability proofs by transitivity gives reachability from u to w in G'.
uses
SimpleGraph.Reachable.rfllemma tree_delete_edge_reconnect_isTree_reachable_of_adj_reachable {V : Type*} {G G' : SimpleGraph V} (h : ∀ ⦃a b : V⦄, G.Adj a b → G'.Reachable a b) {x y : V} (r : G.Reachable x y) : G'.Reachable x y := by obtain ⟨p⟩ := r induction p with | nil => exact SimpleGraph.Reachable.rfl | cons hadj _ ih => exact (h hadj).trans ih
The deleted edge vw is a bridge that disconnects v from w, and u is reachable in T ∖ {vw} to at least one of v or w.
Because T is acyclic, every edge of T is a bridge (`SimpleGraph.isAcyclic_iff_forall_adj_isBridge.mp`), so deleting vw leaves v and w mutually unreachable (`SimpleGraph.isBridge_iff.mp`). We case split on whether u can reach w in T ∖ {vw}: if so, the disjunction holds immediately (`Or.inr`). Otherwise, taking the unique path p from u to v in T, the assumption that u cannot reach w and v cannot reach w implies that the edge vw cannot lie on p (`hp.isTrail.not_mem_edges_of_not_reachable`). Thus p survives in T ∖ {vw}, establishing that u can reach v (`SimpleGraph.reachable_deleteEdges_iff_exists_walk.mpr`).
uses
SimpleGraph.isAcyclic_iff_forall_adj_isBridge.mp,SimpleGraph.isBridge_iff.mp,Or.inr,SimpleGraph.reachable_deleteEdges_iff_exists_walk.mprhave hb : T.IsBridge s(v, w) := SimpleGraph.isAcyclic_iff_forall_adj_isBridge.mp hT.isAcyclic he have hvw : ¬ (T.deleteEdges {s(v, w)}).Reachable v w := SimpleGraph.isBridge_iff.mp hb have h_reach_or : (T.deleteEdges {s(v, w)}).Reachable u v ∨ (T.deleteEdges {s(v, w)}).Reachable u w := by by_cases huw_r : (T.deleteEdges {s(v, w)}).Reachable u w · exact Or.inr huw_r · left obtain ⟨p, hp⟩ := hT.connected.exists_isPath u v have h_not_mem : s(v, w) ∉ p.edges := hp.isTrail.not_mem_edges_of_not_reachable huw_r hvw exact SimpleGraph.reachable_deleteEdges_iff_exists_walk.mpr ⟨p, h_not_mem⟩
There exists a vertex x ∈ {v, w} lying in the component of T ∖ {vw} opposite to u.
From the previous disjunction, if u can reach v in T ∖ {vw}, we set x = w (using `Or.inr` for x = w and `Or.inl` for the reachability conjunction); if u can reach w, we set x = v (using `Or.inl` and `Or.inr`). In either case, x ∈ {v, w} and u is reachable to the other endpoint of the deleted edge.
uses
Or.inl,Or.inrobtain ⟨x, hx_vw, hx_reach⟩ : ∃ x : V, (x = v ∨ x = w) ∧ ((x = w ∧ (T.deleteEdges {s(v, w)}).Reachable u v) ∨ (x = v ∧ (T.deleteEdges {s(v, w)}).Reachable u w)) := by rcases h_reach_or with h | h · exact ⟨w, Or.inr rfl, Or.inl ⟨rfl, h⟩⟩ · exact ⟨v, Or.inl rfl, Or.inr ⟨rfl, h⟩⟩
With this choice of x, u ≠ x and ux is not an edge in T ∖ {vw}.
We provide x as the existential witness. Since u ≠ v and u ≠ w by assumption, u ≠ x. If ux were an edge in T ∖ {vw}, then u and x would be adjacent and hence reachable in T ∖ {vw}, which, combined with the fact that u is reachable to the opposite endpoint of vw, would make v and w reachable in T ∖ {vw}, contradicting that vw was a bridge.
refine ⟨x, hx_vw, ?_⟩ have hux_ne : u ≠ x := by rcases hx_vw with rfl | rfl <;> assumption have hnot : ¬ (T.deleteEdges {s(v, w)}).Adj u x := by intro hadj rcases hx_reach with ⟨rfl, hr⟩ | ⟨rfl, hr⟩ · exact hvw (hr.symm.trans hadj.reachable) · exact hvw (hadj.symm.reachable.trans hr)
To prove that the reconnected graph is a tree, it suffices to prove that it is connected and that its edge count plus one equals the vertex count.
By `SimpleGraph.isTree_iff_connected_and_card`, a graph on a finite vertex type is a tree if and only if it is connected and |E| + 1 = |V|. We split the goal into these two independent obligations.
uses
SimpleGraph.isTree_iff_connected_and_cardrw [SimpleGraph.isTree_iff_connected_and_card] refine ⟨?_, ?_⟩
The reconnected graph G' contains the edge ux, and v and w are reachable from each other in G'.
We define G' as the join of T ∖ {vw} and the single-edge graph on {ux}, noting that T ∖ {vw} ≤ G' (`le_sup_left`). By definition of the graph from an edge set (`SimpleGraph.fromEdgeSet_adj`) and since u ≠ x, ux is an edge in G' (`Set.mem_singleton`, `Or.inr`). Depending on which component u belonged to, u is connected in T ∖ {vw} to one endpoint and connected to the other endpoint x by the edge ux in G'. Tracing through u via this edge establishes that v and w are reachable from each other in G'.
uses
le_sup_left,SimpleGraph.fromEdgeSet_adj,Set.mem_singleton,Or.inr· have : Nonempty V := hT.connected.nonempty let G' := T.deleteEdges {s(v, w)} ⊔ SimpleGraph.fromEdgeSet {s(u, x)} have h_le : T.deleteEdges {s(v, w)} ≤ G' := le_sup_left have h_ux : G'.Adj u x := by apply Or.inr rw [SimpleGraph.fromEdgeSet_adj] rcases hx_reach with ⟨rfl, -⟩ | ⟨rfl, -⟩ · exact ⟨Set.mem_singleton _, huw⟩ · exact ⟨Set.mem_singleton _, huv⟩ have hvw' : G'.Reachable v w := by rcases hx_reach with ⟨rfl, hr⟩ | ⟨rfl, hr⟩ · exact (hr.mono h_le).symm.trans h_ux.reachable · exact (h_ux.symm.reachable).trans (hr.mono h_le)
The reconnected graph G' is connected.
We show that every adjacent pair a, b in the original tree T is reachable in G'. If {a, b} = {v, w} (`Sym2.eq_iff`), they are reachable by the previous step. Otherwise, ab is not the edge vw, so ab is an edge in T ∖ {vw} (`SimpleGraph.deleteEdges_adj`), hence an edge in G', making a and b reachable. Applying the helper lemma `tree_delete_edge_reconnect_isTree_reachable_of_adj_reachable` with the connectedness of T, every pair of vertices in V is reachable in G' (G' is preconnected). Since T is connected, V is nonempty, so G' is connected.
uses
Sym2.eq_iff,SimpleGraph.deleteEdges_adj,tree_delete_edge_reconnect_isTree_reachable_of_adj_reachablehave hadj : ∀ ⦃a b : V⦄, T.Adj a b → G'.Reachable a b := by intro a b hab by_cases h_eq : s(a, b) = s(v, w) · rw [Sym2.eq_iff] at h_eq rcases h_eq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact hvw' · exact hvw'.symm · have h_del : (T.deleteEdges {s(v, w)}).Adj a b := by rw [SimpleGraph.deleteEdges_adj] exact ⟨hab, h_eq⟩ exact (h_le h_del).reachable have h_pre : G'.Preconnected := by intro a b exact tree_delete_edge_reconnect_isTree_reachable_of_adj_reachable hadj (hT.connected.preconnected a b) exact ⟨h_pre⟩
The edge count of G' satisfies |E(G')| + 1 = |V|, completing the proof that G' is a tree.
The edge set of the single-edge graph is {s(u, x)} (`SimpleGraph.edgeSet_fromEdgeSet`) since u ≠ x, and the edge set of T ∖ {vw} is E(T) ∖ {s(v, w)}. Their join has edge set equal to inserting s(u, x) into E(T) ∖ {s(v, w)} (`SimpleGraph.edgeSet_sup`, `Set.union_singleton`). Because s(u, x) was not in E(T) ∖ {s(v, w)}, inserting it increases the cardinality by 1 (`Set.ncard_insert_of_notMem`, `mt`), while deleting s(v, w) (an edge of T) decreased it by 1 (`Set.ncard_sdiff_singleton_add_one`). Translating via `Nat.card_coe_set_eq`, the number of edges in G' equals |E(T)|. Since T is a tree, |E(T)| + 1 = |V| (`is_tree_iff_is_acyclic_and_card`), concluding the proof.
uses
SimpleGraph.edgeSet_fromEdgeSet,SimpleGraph.edgeSet_sup,Set.union_singleton,mt,is_tree_iff_is_acyclic_and_card,Nat.card_coe_set_eq,Set.ncard_insert_of_notMem,Set.ncard_sdiff_singleton_add_one· have h_edge : (SimpleGraph.fromEdgeSet {s(u, x)} : SimpleGraph V).edgeSet = {s(u, x)} := by simp [SimpleGraph.edgeSet_fromEdgeSet, hux_ne] have h_del : (T.deleteEdges {s(v, w)}).edgeSet = T.edgeSet \ {s(v, w)} := by simp have h_sup : (T.deleteEdges {s(v, w)} ⊔ SimpleGraph.fromEdgeSet {s(u, x)}).edgeSet = insert s(u, x) (T.edgeSet \ {s(v, w)}) := by rw [SimpleGraph.edgeSet_sup, h_del, h_edge, Set.union_singleton] have h_not_mem : s(u, x) ∉ T.edgeSet \ {s(v, w)} := by rw [← h_del] exact mt (T.deleteEdges {s(v, w)}).mem_edgeSet.mp hnot have h_card_T : Nat.card T.edgeSet + 1 = Nat.card V := (is_tree_iff_is_acyclic_and_card T).mp hT |>.2 rw [Nat.card_coe_set_eq, h_sup, Set.ncard_insert_of_notMem h_not_mem, Set.ncard_sdiff_singleton_add_one (T.mem_edgeSet.mpr he), ← Nat.card_coe_set_eq] exact h_card_T
SimpleGraph.Reachable.rfl- In any graph, every vertex is reachable from itself by the empty walk.
SimpleGraph.isAcyclic_iff_forall_adj_isBridge.mp- In an acyclic graph, every edge is a bridge.
SimpleGraph.isBridge_iff.mp- Deleting a bridge from a graph leaves its endpoints unreachable from each other.
Or.inr- From a proof of B, infer the disjunction A ∨ B.
SimpleGraph.reachable_deleteEdges_iff_exists_walk.mpr- Two vertices are reachable in G ∖ s if there exists a walk between them in G containing no edges from s.
Or.inl- From a proof of A, infer the disjunction A ∨ B.
SimpleGraph.isTree_iff_connected_and_card- A simple graph on a finite vertex type is a tree if and only if it is connected and its edge count plus one equals the number of vertices.
le_sup_left- In a join-semilattice (such as graphs under subgraph inclusion), a ≤ a ⊔ b.
SimpleGraph.fromEdgeSet_adj- Vertices v and w are adjacent in the graph generated by edge set s if and only if {v, w} ∈ s and v ≠ w.
Set.mem_singleton- An element a belongs to the singleton set {a}.
Sym2.eq_iff- Two unordered pairs {x, y} and {z, w} are equal if and only if (x = z ∧ y = w) ∨ (x = w ∧ y = z).
SimpleGraph.deleteEdges_adj- Vertices v and w are adjacent in G ∖ s if and only if they are adjacent in G and the edge {v, w} is not in s.
tree_delete_edge_reconnect_isTree_reachable_of_adj_reachable- If every edge of G connects a pair reachable in G', then any pair reachable in G is also reachable in G'.
SimpleGraph.edgeSet_fromEdgeSet- The edge set of the graph built from a set of pairs s is s minus self-loops.
SimpleGraph.edgeSet_sup- The edge set of the union (join) of two graphs is the union of their edge sets.
Set.union_singleton- The union of a set s with a singleton {a} equals insert a s.
mt- Modus tollens: if A implies B, then ¬B implies ¬A.
is_tree_iff_is_acyclic_and_card- A graph on a finite vertex type is a tree if and only if it is acyclic and its edge count plus one equals its vertex count.
Nat.card_coe_set_eq- The cardinality Nat.card of a coerced set is equal to its set cardinality ncard.
Set.ncard_insert_of_notMem- Inserting an element a ∉ s into a finite set s increases its cardinality by 1.
Set.ncard_sdiff_singleton_add_one- For an element a ∈ s in a finite set s, |s ∖ {a}| + 1 = |s|.
- The tree characterization used (`SimpleGraph.isTree_iff_connected_and_card`) requires showing connectedness and the edge count formula |E| + 1 = |V|, bypassing the need to check acyclicity of the reconnected graph directly.
- The proof transitions between type cardinality (`Nat.card`) and set cardinality (`Set.ncard`) via `Nat.card_coe_set_eq` when computing the number of edges.
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 tree_delete_edge_reconnect_isTree_reachable_of_adj_reachable {V : Type*} {G G' : SimpleGraph V} (h : ∀ ⦃a b : V⦄, G.Adj a b → G'.Reachable a b) {x y : V} (r : G.Reachable x y) : G'.Reachable x y := by obtain ⟨p⟩ := r induction p with | nil => exact SimpleGraph.Reachable.rfl | cons hadj _ ih => exact (h hadj).trans ih/-- Deleting an edge not incident to u in a tree can be reconnected by joining u to one of the edge's endpoints to form a tree. -/theorem tree_delete_edge_reconnect_isTree {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (hT : T.IsTree) (u v w : V) (he : T.Adj v w) (huv : u ≠ v) (huw : u ≠ w) : ∃ x : V, (x = v ∨ x = w) ∧ (T.deleteEdges {s(v, w)} ⊔ SimpleGraph.fromEdgeSet {s(u, x)}).IsTree := by have hb : T.IsBridge s(v, w) := SimpleGraph.isAcyclic_iff_forall_adj_isBridge.mp hT.isAcyclic he have hvw : ¬ (T.deleteEdges {s(v, w)}).Reachable v w := SimpleGraph.isBridge_iff.mp hb have h_reach_or : (T.deleteEdges {s(v, w)}).Reachable u v ∨ (T.deleteEdges {s(v, w)}).Reachable u w := by by_cases huw_r : (T.deleteEdges {s(v, w)}).Reachable u w · exact Or.inr huw_r · left obtain ⟨p, hp⟩ := hT.connected.exists_isPath u v have h_not_mem : s(v, w) ∉ p.edges := hp.isTrail.not_mem_edges_of_not_reachable huw_r hvw exact SimpleGraph.reachable_deleteEdges_iff_exists_walk.mpr ⟨p, h_not_mem⟩ obtain ⟨x, hx_vw, hx_reach⟩ : ∃ x : V, (x = v ∨ x = w) ∧ ((x = w ∧ (T.deleteEdges {s(v, w)}).Reachable u v) ∨ (x = v ∧ (T.deleteEdges {s(v, w)}).Reachable u w)) := by rcases h_reach_or with h | h · exact ⟨w, Or.inr rfl, Or.inl ⟨rfl, h⟩⟩ · exact ⟨v, Or.inl rfl, Or.inr ⟨rfl, h⟩⟩ refine ⟨x, hx_vw, ?_⟩ have hux_ne : u ≠ x := by rcases hx_vw with rfl | rfl <;> assumption have hnot : ¬ (T.deleteEdges {s(v, w)}).Adj u x := by intro hadj rcases hx_reach with ⟨rfl, hr⟩ | ⟨rfl, hr⟩ · exact hvw (hr.symm.trans hadj.reachable) · exact hvw (hadj.symm.reachable.trans hr) rw [SimpleGraph.isTree_iff_connected_and_card] refine ⟨?_, ?_⟩ · have : Nonempty V := hT.connected.nonempty let G' := T.deleteEdges {s(v, w)} ⊔ SimpleGraph.fromEdgeSet {s(u, x)} have h_le : T.deleteEdges {s(v, w)} ≤ G' := le_sup_left have h_ux : G'.Adj u x := by apply Or.inr rw [SimpleGraph.fromEdgeSet_adj] rcases hx_reach with ⟨rfl, -⟩ | ⟨rfl, -⟩ · exact ⟨Set.mem_singleton _, huw⟩ · exact ⟨Set.mem_singleton _, huv⟩ have hvw' : G'.Reachable v w := by rcases hx_reach with ⟨rfl, hr⟩ | ⟨rfl, hr⟩ · exact (hr.mono h_le).symm.trans h_ux.reachable · exact (h_ux.symm.reachable).trans (hr.mono h_le) have hadj : ∀ ⦃a b : V⦄, T.Adj a b → G'.Reachable a b := by intro a b hab by_cases h_eq : s(a, b) = s(v, w) · rw [Sym2.eq_iff] at h_eq rcases h_eq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact hvw' · exact hvw'.symm · have h_del : (T.deleteEdges {s(v, w)}).Adj a b := by rw [SimpleGraph.deleteEdges_adj] exact ⟨hab, h_eq⟩ exact (h_le h_del).reachable have h_pre : G'.Preconnected := by intro a b exact tree_delete_edge_reconnect_isTree_reachable_of_adj_reachable hadj (hT.connected.preconnected a b) exact ⟨h_pre⟩ · have h_edge : (SimpleGraph.fromEdgeSet {s(u, x)} : SimpleGraph V).edgeSet = {s(u, x)} := by simp [SimpleGraph.edgeSet_fromEdgeSet, hux_ne] have h_del : (T.deleteEdges {s(v, w)}).edgeSet = T.edgeSet \ {s(v, w)} := by simp have h_sup : (T.deleteEdges {s(v, w)} ⊔ SimpleGraph.fromEdgeSet {s(u, x)}).edgeSet = insert s(u, x) (T.edgeSet \ {s(v, w)}) := by rw [SimpleGraph.edgeSet_sup, h_del, h_edge, Set.union_singleton] have h_not_mem : s(u, x) ∉ T.edgeSet \ {s(v, w)} := by rw [← h_del] exact mt (T.deleteEdges {s(v, w)}).mem_edgeSet.mp hnot have h_card_T : Nat.card T.edgeSet + 1 = Nat.card V := (is_tree_iff_is_acyclic_and_card T).mp hT |>.2 rw [Nat.card_coe_set_eq, h_sup, Set.ncard_insert_of_notMem h_not_mem, Set.ncard_sdiff_singleton_add_one (T.mem_edgeSet.mpr he), ← Nat.card_coe_set_eq] exact h_card_T