AFTD Auto-Formalizing Theoretical Domains

op223_slide_leaf_pendant_chain_is_tree

theoremverified

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

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.

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

    lines 9–12

    uses SimpleGraph.isTree_iff_connected_and_card.mp

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

    lines 13–15

      have hvb_ne : v ≠ b := by
        rintro rfl
        exact hb p.end_mem_support
  3. 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'.

    lines 16–20

    uses SimpleGraph.sup_adj, SimpleGraph.fromEdgeSet_adj

      have h_vb_adj : X'.Adj v b := by
        rw [SimpleGraph.sup_adj]
        right
        rw [SimpleGraph.fromEdgeSet_adj]
        exact ⟨rfl, hvb_ne⟩
  4. 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'.

    lines 21–30

    uses SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges, Sym2.mem_mk_right, Set.mem_singleton_iff.mp

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

    lines 31–32

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

    lines 33–45

    uses Sym2.eq_iff, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, Set.mem_singleton_iff.mp

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

    lines 46–52

    uses SimpleGraph.Reachable.refl

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

    lines 53–61

    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_iff

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

    lines 62–71

    uses SimpleGraph.mem_edgeSet, Set.union_singleton, Set.ncard_insert_of_notMem, Set.ncard_sdiff_singleton_add_one

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

    lines 72–75

    uses Nat.card_coe_set_eq, SimpleGraph.isTree_iff_connected_and_card.mpr

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

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

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