AFTD Auto-Formalizing Theoretical Domains

tree_delete_edge_reconnect_isTree

theoremverified

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

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.

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

    lines 1–9

    uses SimpleGraph.Reachable.rfl

    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
  2. 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`).

    lines 18–30

    uses SimpleGraph.isAcyclic_iff_forall_adj_isBridge.mp, SimpleGraph.isBridge_iff.mp, Or.inr, SimpleGraph.reachable_deleteEdges_iff_exists_walk.mpr

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

    lines 31–36

    uses Or.inl, Or.inr

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

    lines 37–43

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

    lines 44–45

    uses SimpleGraph.isTree_iff_connected_and_card

      rw [SimpleGraph.isTree_iff_connected_and_card]
      refine ⟨?_, ?_⟩
  6. 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'.

    lines 46–58

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

    lines 59–73

    uses Sym2.eq_iff, SimpleGraph.deleteEdges_adj, tree_delete_edge_reconnect_isTree_reachable_of_adj_reachable

        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⟩
  8. 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.

    lines 74–87

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

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