AFTD Auto-Formalizing Theoretical Domains

op223_gts_is_tree

theoremverifiedformalization

For any simple graphs T and T' on a type V, if T' is obtained from T by a generalized tree shift, then T' is a tree.

Statement

theorem op223_gts_is_tree {V : Type*} (T T' : SimpleGraph V)
    (h : is_generalized_tree_shift T T') :
    T'.IsTree
Formalizes
arXiv:2610.17078 Section 2
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • is_generalized_tree_shiftA simple graph T' on an arbitrary type V is obtained from a tree T by a generalized tree shift if T is a tree, and there exist distinct…
  • gts_graphThe graph obtained from T by deleting all edges between candidate v and its neighbours other than w, and inserting edges between…
  • Arena.Reachable.transReachability is transitive.
Used by 1
  • op223_shift_bad_edge_yields_stepIf a nonsustainable tree undergoes an adjacent shift and a retained beneficiary edge remains nonsustainable, the shift is a step between…

Read back from the Lean

For any type V and any simple graphs T and T' on V, if T' is obtained from T by a generalized tree shift (is_generalized_tree_shift T T'), then T' is a tree (T'.IsTree).

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

A generalized tree shift modifies a tree T along a path p from u to v by replacing all edges from v to neighbors outside p with edges from u to those same neighbors. The proof shows that the modified graph T' is a tree by first showing it is connected: the path p is preserved and connects u to v, which suffices to restore reachability between any disconnected endpoints. Second, acyclicity is proved by contradiction: any hypothetical cycle in T' containing new edges can be rooted at u, leaving an internal subwalk in T whose endpoints force it to contain one of the deleted bridge edges (by two key separation lemmas), while a cycle without new edges would already be a cycle in T.

  1. An unordered pair s(a, b) belongs to the set {e | ∃ z, e = s(x, z) ∧ P z} if and only if (a = x ∧ P b) ∨ (b = x ∧ P a).

    By unfolding set membership and the equality condition for unordered pairs in Sym2, s(a, b) = s(x, z) holds if and only if (a = x ∧ b = z) or (a = z ∧ b = x). Substituting z in each case establishes the equivalence.

    lines 1–12

    uses Set.mem_ofPred_eq, Sym2.eq_iff, Or.inl, Or.inr, Sym2.eq_swap

    lemma op223_gts_is_tree_sym2_mem {V : Type*} {x : V} (P : V → Prop) (a b : V) :
        s(a, b) ∈ {e : Sym2 V | ∃ z, e = s(x, z) ∧ P z} ↔ (a = x ∧ P b) ∨ (b = x ∧ P a) := by
      simp only [Set.mem_ofPred_eq]
      constructor
      · rintro ⟨z, he, hP⟩
        rw [Sym2.eq_iff] at he
        rcases he with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩
        · exact Or.inl ⟨rfl, hP⟩
        · exact Or.inr ⟨rfl, hP⟩
      · rintro (⟨rfl, hP⟩ | ⟨rfl, hP⟩)
        · exact ⟨b, rfl, hP⟩
        · exact ⟨a, Sym2.eq_swap, hP⟩
  2. Unpack the generalized tree shift: endpoints u and v, path p, penultimate vertex w, shifted neighbor set A, deleted edges F, added edges N, and the acyclicity of T.

    From the hypothesis that T' is a generalized tree shift of T, we obtain the tree structure of T, the path p connecting distinct endpoints u and v, and the penultimate vertex w along p. We define A as the neighbors of v other than w, F as the edges between v and A, and N as the edges between u and A. By definition, T' deletes F and adds N, and T is acyclic.

    lines 18–25

      classical
      obtain ⟨hT, u, v, p, hp, huv, hdeg, hTeq⟩ := h
      set w : V := p.penultimate with hw
      set A : Set V := {z | T.Adj v z ∧ z ≠ w} with hA
      set F : Set (Sym2 V) := {e | ∃ z, e = s(v, z) ∧ T.Adj v z ∧ z ≠ w} with hF
      set N : Set (Sym2 V) := {e | ∃ z, e = s(u, z) ∧ T.Adj v z ∧ z ≠ w} with hN
      have hT'eq : T' = T.deleteEdges F ⊔ SimpleGraph.fromEdgeSet N := hTeq
      have hTacyc : T.IsAcyclic := hT.isAcyclic
  3. Neither u nor v belongs to A.

    If u were in A, it would be a neighbor of v lying on the path p; in the tree T, the only neighbor of v on p is the penultimate vertex w, which contradicts u ≠ w. Furthermore, v ∉ A because simple graphs have no self-loops.

    lines 26–32

    uses Set.mem_ofPred_eq, SimpleGraph.irrefl

      have huA : u ∉ A := by
        simp only [hA, Set.mem_ofPred_eq]
        rintro ⟨hadj, hne⟩
        exact hne (hTacyc.eq_penultimate_of_adj_end hp hadj p.start_mem_support)
      have hvA : v ∉ A := by
        simp only [hA, Set.mem_ofPred_eq]
        exact fun h => SimpleGraph.irrefl T h.1
  4. The sets F and N are characterized by their endpoints with A, they are disjoint, and no edge of F remains in T'.

    Using the helper lemma, an edge is in F (respectively N) if and only if one endpoint is v (respectively u) and the other is in A. Since u ≠ v and neither u nor v is in A, F and N are disjoint. Consequently, no edge of F is in the edge set of T' = (T \ F) ∪ N.

    lines 33–58

    uses op223_gts_is_tree_sym2_mem, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges, SimpleGraph.edgeSet_fromEdgeSet

      have hFs : ∀ a b : V, s(a,b) ∈ F ↔ (a = v ∧ b ∈ A) ∨ (b = v ∧ a ∈ A) := by
        intro a b
        rw [hF, hA]
        exact op223_gts_is_tree_sym2_mem (fun z => T.Adj v z ∧ z ≠ w) a b
      have hNs : ∀ a b : V, s(a,b) ∈ N ↔ (a = u ∧ b ∈ A) ∨ (b = u ∧ a ∈ A) := by
        intro a b
        rw [hN, hA]
        exact op223_gts_is_tree_sym2_mem (fun z => T.Adj v z ∧ z ≠ w) a b
      have hFN : ∀ a b : V, s(a,b) ∈ F → s(a,b) ∈ N → False := by
        intro a b hf hn
        rw [hFs] at hf
        rw [hNs] at hn
        rcases hf with ⟨rfl, hbA⟩ | ⟨rfl, haA⟩
        · rcases hn with ⟨ha, -⟩ | ⟨hb, -⟩
          · exact huv ha.symm
          · rw [hb] at hbA; exact huA hbA
        · rcases hn with ⟨ha, -⟩ | ⟨hb, -⟩
          · rw [ha] at haA; exact huA haA
          · exact huv hb.symm
      have hFT' : ∀ a b : V, s(a,b) ∈ F → s(a,b) ∉ T'.edgeSet := by
        intro a b habF habT'
        rw [hT'eq, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges,
          SimpleGraph.edgeSet_fromEdgeSet] at habT'
        rcases habT' with ⟨-, h2⟩ | ⟨h2, -⟩
        · exact h2 habF
        · exact hFN a b habF h2
  5. Vertices a and b are adjacent in T' if and only if they are adjacent in T with edge not in F, or their edge belongs to N.

    Adjacency in T' = (T \ F) ⊔ (SimpleGraph.fromEdgeSet N) means either adjacency in T with edge not in F, or membership in N with distinct endpoints. For any edge in N, the endpoints cannot coincide because u ∉ A.

    lines 59–74

    uses SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Or.inl, Or.inr

      have hT'adj : ∀ a b : V, T'.Adj a b ↔ (T.Adj a b ∧ s(a,b) ∉ F) ∨ s(a,b) ∈ N := by
        intro a b
        rw [hT'eq, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj]
        constructor
        · rintro (⟨h1, h2⟩ | ⟨h1, h2⟩)
          · exact Or.inl ⟨h1, h2⟩
          · exact Or.inr h1
        · rintro (⟨h1, h2⟩ | h1)
          · exact Or.inl ⟨h1, h2⟩
          · have hd : a ≠ b := by
              rintro rfl
              rw [hNs] at h1
              rcases h1 with ⟨h1, h2⟩ | ⟨h1, h2⟩
              · rw [h1] at h2; exact huA h2
              · rw [h1] at h2; exact huA h2
            exact Or.inr ⟨h1, hd⟩
  6. No edge of p belongs to F, so p remains a walk in T' and u, v are mutually reachable in T'.

    Any edge in F is incident to v and some z ∈ A with z ≠ w. If such an edge were on p, z would be on the path support and adjacent to v, forcing z = w, a contradiction. Hence all edges of p survive in T', making v and u reachable from one another.

    lines 75–87

    uses SimpleGraph.Walk.snd_mem_support_of_mem_edges, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges, SimpleGraph.edgeSet_fromEdgeSet, Or.inl

      have hpF : ∀ e ∈ p.edges, e ∉ F := by
        intro e he heF
        rw [hF] at heF
        obtain ⟨z, rfl, hzv, hzw⟩ := heF
        exact hzw (hTacyc.eq_penultimate_of_adj_end hp hzv
          (SimpleGraph.Walk.snd_mem_support_of_mem_edges p he))
      have hpT' : ∀ e ∈ p.edges, e ∈ T'.edgeSet := by
        intro e he
        rw [hT'eq, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges,
          SimpleGraph.edgeSet_fromEdgeSet]
        exact Or.inl ⟨p.edges_subset_edgeSet he, hpF e he⟩
      have hpwalk : T'.Walk u v := p.transfer T' hpT'
      have hpReach : T'.Reachable v u := ⟨hpwalk.reverse⟩
  7. The graph T' is connected.

    Every edge of T not in F remains in T'. For an edge in F connecting v to z ∈ A, the replacement edge {u, z} is in T', and since v can reach u via p, v and z remain reachable in T'. Reachability in T therefore implies reachability in T' by path induction, so T' is preconnected and, having vertices, connected.

    lines 88–103

    uses Or.inl, Or.inr, SimpleGraph.reachable_iff_reflTransGen, SimpleGraph.Reachable.rfl, SimpleGraph.connected_iff

      have hstep : ∀ a b : V, T.Adj a b → T'.Reachable a b := by
        intro a b hab
        by_cases hFab : s(a,b) ∈ F
        · rw [hFs] at hFab
          rcases hFab with ⟨rfl, hbA⟩ | ⟨rfl, haA⟩
          · exact hpReach.trans ((hT'adj u b).mpr (Or.inr ((hNs u b).mpr (Or.inl ⟨rfl, hbA⟩)))).reachable
          · exact (hpReach.trans ((hT'adj u a).mpr (Or.inr ((hNs u a).mpr (Or.inl ⟨rfl, haA⟩)))).reachable).symm
        · exact ((hT'adj a b).mpr (Or.inl ⟨hab, hFab⟩)).reachable
      have hpre : T'.Preconnected := by
        intro a b
        have hab : T.Reachable a b := hT.connected.preconnected a b
        rw [SimpleGraph.reachable_iff_reflTransGen] at hab
        induction hab with
        | refl => exact SimpleGraph.Reachable.rfl
        | tail _ hbc ih => exact ih.trans (hstep _ _ hbc)
      have hconn : T'.Connected := (SimpleGraph.connected_iff T').mpr ⟨hpre, hT.connected.nonempty⟩
  8. For each z ∈ A, {v, z} is a bridge in T, and the path p avoids {v, z}.

    Since T is a tree, every edge is a bridge, so deleting {v, z} disconnects v from z. The path p contains no edges of F and thus avoids {v, z}, remaining a valid walk between u and v in T \ {{v, z}}.

    lines 104–123

    uses SimpleGraph.edgeSet_deleteEdges, Or.inl

      have hbridgeA : ∀ z ∈ A, ¬ (T.deleteEdges {s(v,z)}).Reachable v z := by
        intro z hz
        have hb : T.IsBridge s(v, z) := SimpleGraph.isAcyclic_iff_forall_adj_isBridge.mp hTacyc hz.1
        exact SimpleGraph.isBridge_iff.mp hb
      have hptrans : ∀ z ∈ A, (T.deleteEdges {s(v,z)}).Walk u v := by
        intro z hz
        refine p.transfer _ (fun e he => ?_)
        rw [SimpleGraph.edgeSet_deleteEdges]
        refine ⟨p.edges_subset_edgeSet he, ?_⟩
        simp only [Set.mem_singleton_iff]
        intro hh
        exact hpF e he (hh ▸ ((hFs v z).mpr (Or.inl ⟨rfl, hz⟩)))
      have hFs' : ∀ z : V, s(v,z) ∈ F ↔ z ∈ A := by
        intro z
        rw [hFs]
        exact ⟨fun h => h.elim (fun h => h.2) (fun h => absurd h.2 hvA), fun h => Or.inl ⟨rfl, h⟩⟩
      have hNleft : ∀ z : V, s(u,z) ∈ N ↔ z ∈ A := by
        intro z
        rw [hNs]
        exact ⟨fun h => h.elim (fun h => h.2) (fun h => absurd h.2 huA), fun h => Or.inl ⟨rfl, h⟩⟩
  9. In T, any walk between distinct z₁, z₂ ∈ A must use {v, z₁}, and any walk from z ∈ A to a neighbor y of u with {y, u} ∉ F must use {v, z}.

    Both separation properties (KL2 and KL3) are proved by contradiction. If a walk between z₁ and z₂ avoided {v, z₁}, then z₁ could reach z₂ and then v in T \ {{v, z₁}}, contradicting that {v, z₁} is a bridge. Similarly, if a walk from z to y avoided {v, z}, then z could reach y, then u, then v via p in T \ {{v, z}}, again contradicting the bridge property.

    lines 124–160

    uses SimpleGraph.reachable_deleteEdges_iff_exists_walk, SimpleGraph.deleteEdges_adj, Sym2.eq_iff, SimpleGraph.irrefl

      have KL2 : ∀ z₁ z₂ : V, z₁ ∈ A → z₂ ∈ A → z₁ ≠ z₂ →
          ∀ W : T.Walk z₁ z₂, s(v,z₁) ∈ W.edges := by
        intro z₁ z₂ h1 h2 hne W
        by_contra hcon
        apply hbridgeA z₁ h1
        have hW1 : (T.deleteEdges {s(v,z₁)}).Reachable z₁ z₂ := by
          rw [SimpleGraph.reachable_deleteEdges_iff_exists_walk]
          exact ⟨W, hcon⟩
        have hW2 : (T.deleteEdges {s(v,z₁)}).Reachable z₂ v := by
          have hadj : (T.deleteEdges {s(v,z₁)}).Adj z₂ v := by
            rw [SimpleGraph.deleteEdges_adj]
            refine ⟨h2.1.symm, ?_⟩
            simp only [Set.mem_singleton_iff]
            intro hh
            rw [Sym2.eq_iff] at hh
            rcases hh with ⟨-, h'⟩ | ⟨h', -⟩
            · exact SimpleGraph.irrefl T (h' ▸ h1.1)
            · exact hne h'.symm
          exact hadj.reachable
        exact (hW1.trans hW2).symm
      have KL3 : ∀ z y : V, z ∈ A → T.Adj y u → s(y,u) ∉ F →
          ∀ W : T.Walk z y, s(v,z) ∈ W.edges := by
        intro z y hz hadj hnotF W
        by_contra hcon
        apply hbridgeA z hz
        have hW1 : (T.deleteEdges {s(v,z)}).Reachable z y := by
          rw [SimpleGraph.reachable_deleteEdges_iff_exists_walk]
          exact ⟨W, hcon⟩
        have hW2 : (T.deleteEdges {s(v,z)}).Reachable y v := by
          have hadj' : (T.deleteEdges {s(v,z)}).Adj y u := by
            rw [SimpleGraph.deleteEdges_adj]
            refine ⟨hadj, ?_⟩
            simp only [Set.mem_singleton_iff]
            intro hh
            exact hnotF (hh ▸ ((hFs v z).mpr (Or.inl ⟨rfl, hz⟩)))
          exact hadj'.reachable.trans ⟨hptrans z hz⟩
        exact (hW1.trans hW2).symm
  10. To show T' is a tree, it suffices to prove it has no cycles; any edge in a walk in T' is either an edge of T or an edge of N.

    With connectivity established, treehood reduces to acyclicity. Any edge appearing on a walk in T' belongs to T'.edgeSet, which is contained in T.edgeSet ∪ N.

    lines 161–171

    uses SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges, SimpleGraph.edgeSet_fromEdgeSet, Or.inl, Or.inr

      refine ⟨hconn, ?_⟩
      intro x₀ c hc
      have hedgeT' : ∀ {a b : V} (W : T'.Walk a b) ⦃e : Sym2 V⦄, e ∈ W.edges →
          e ∈ T.edgeSet ∨ e ∈ N := by
        intro a b W e he
        have h1 : e ∈ T'.edgeSet := W.edges_subset_edgeSet he
        rw [hT'eq, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges,
          SimpleGraph.edgeSet_fromEdgeSet] at h1
        rcases h1 with ⟨hh, -⟩ | ⟨hh, -⟩
        · exact Or.inl hh
        · exact Or.inr hh
  11. If a cycle c in T' contains an edge of N, rotating c to start at u produces an internal subwalk M whose edges all belong to T and none to F.

    Every edge in N has u as an endpoint, so u is in the vertex support of c. Rotating c yields a cycle c' based at u. Decomposing c' into its first step from u, its penultimate step to u, and the intermediate subwalk M, the nodup property of cycle vertices ensures u ∉ M.support. Since every edge of N contains u, M cannot contain any edge of N, meaning all its edges are in T and none are in F.

    lines 172–206

    uses SimpleGraph.Walk.fst_mem_support_of_mem_edges, SimpleGraph.Walk.not_nil_iff_lt_length, SimpleGraph.Walk.length_tail, SimpleGraph.Walk.support_dropLast, SimpleGraph.Walk.support_tail_of_not_nil, SimpleGraph.Walk.dropLast_support_concat

      by_cases hnew : ∃ e ∈ c.edges, e ∈ N
      · obtain ⟨e₀, he₀, he₀N⟩ := hnew
        have husupp : u ∈ c.support := by
          rw [hN] at he₀N
          obtain ⟨z, rfl, -⟩ := he₀N
          exact SimpleGraph.Walk.fst_mem_support_of_mem_edges c he₀
        set c' : T'.Walk u u := c.rotate u husupp with hc'def
        have hc' : c'.IsCycle := hc.rotate husupp
        have hlen : 3 ≤ c'.length := hc'.isCircuit.three_le_length
        have htnn : ¬ c'.tail.Nil := by
          rw [SimpleGraph.Walk.not_nil_iff_lt_length, SimpleGraph.Walk.length_tail]; omega
        set y : V := (c'.tail).penultimate with hy
        let M : T'.Walk c'.snd y := (c'.tail).dropLast
        have hMsupp : M.support = (c'.tail.support).dropLast :=
          SimpleGraph.Walk.support_dropLast htnn
        have htnod : (c'.tail.support).Nodup := by
          rw [SimpleGraph.Walk.support_tail_of_not_nil c' hc'.not_nil]
          exact hc'.support_nodup
        have huM : u ∉ M.support := by
          rw [hMsupp]
          have hl : (c'.tail.support).dropLast ++ [u] = c'.tail.support :=
            SimpleGraph.Walk.dropLast_support_concat c'.tail
          have hnod : ((c'.tail.support).dropLast ++ [u]).Nodup := by rw [hl]; exact htnod
          intro hmem
          exact (List.nodup_append.mp hnod).2.2 u hmem u (by simp) rfl
        have hMT : ∀ e ∈ M.edges, e ∈ T.edgeSet := by
          intro e he
          rcases hedgeT' M he with hh | hh
          · exact hh
          · rw [hN] at hh
            obtain ⟨z, rfl, -⟩ := hh
            exact absurd (SimpleGraph.Walk.fst_mem_support_of_mem_edges M he) huM
        have hMF : ∀ a b : V, s(a,b) ∈ M.edges → s(a,b) ∉ F := by
          intro a b he
          exact fun hF' => hFT' a b hF' (M.edges_subset_edgeSet he)
  12. Decompose the edge list of c' as s(u, c'.snd) :: (M.edges ++ [s(y, u)]), with the first and last edges belonging to N if and only if c'.snd ∈ A and y ∈ A.

    Reconstructing the walk c' from its head step, internal walk M, and final step produces the exact edge list. Membership of the end edges in N corresponds directly to whether their other endpoints lie in A.

    lines 207–222

    uses SimpleGraph.Walk.cons_tail_eq, SimpleGraph.Walk.concat_dropLast, SimpleGraph.Walk.adj_penultimate, SimpleGraph.Walk.edges_concat, List.concat_eq_append, List.mem_cons_of_mem, List.mem_append_right, List.mem_cons_self, Or.inr

        have hcedges1 : c'.edges = s(u, c'.snd) :: c'.tail.edges := by
          nth_rewrite 1 [← SimpleGraph.Walk.cons_tail_eq c' hc'.not_nil]
          simp [SimpleGraph.Walk.edges_cons]
        have hcedges2 : c'.tail.edges = M.edges ++ [s(y, u)] := by
          conv_lhs => rw [← SimpleGraph.Walk.concat_dropLast (p := c'.tail) (SimpleGraph.Walk.adj_penultimate htnn)]
          rw [SimpleGraph.Walk.edges_concat, List.concat_eq_append]
        have hcedges : c'.edges = s(u, c'.snd) :: (M.edges ++ [s(y, u)]) := by
          rw [hcedges1, hcedges2]
        have hyN : s(y, u) ∈ N ↔ y ∈ A := by
          rw [hNs]
          exact ⟨fun h => h.elim (fun h => h.1 ▸ h.2) (fun h => h.2), fun h => Or.inr ⟨rfl, h⟩⟩
        have hmem_last : s(y, u) ∈ c'.edges := by
          rw [hcedges]
          exact List.mem_cons_of_mem _ (List.mem_append_right _ (List.mem_singleton.mpr rfl))
        have hmem_first : s(u, c'.snd) ∈ c'.edges := by
          rw [hcedges]; exact List.mem_cons_self ..
  13. A contradiction arises if c'.snd ∈ A, whether y ∈ A or y ∉ A.

    If both c'.snd and y are in A, they are distinct since c' has distinct edges; by KL2, the walk M in T must contain {v, c'.snd} ∈ F, contradicting that M contains no edges of F. If y ∉ A, the edge {y, u} must be an edge of T not in F; by KL3, M must again contain {v, c'.snd} ∈ F, another contradiction.

    lines 223–241

    uses List.nodup_cons, List.mem_append_right, Sym2.eq_swap, SimpleGraph.Walk.edges_transfer, SimpleGraph.mem_edgeSet

        by_cases hxA : c'.snd ∈ A
        · by_cases hyA : y ∈ A
          · have hxy : c'.snd ≠ y := by
              intro hxy'
              have hnod := hc'.isCircuit.isTrail.edges_nodup
              rw [hcedges] at hnod
              rw [List.nodup_cons] at hnod
              exact hnod.1 (List.mem_append_right _ (List.mem_singleton.mpr (by rw [hxy']; exact Sym2.eq_swap.symm)))
            have hkl := KL2 c'.snd y hxA hyA hxy (M.transfer T hMT)
            rw [SimpleGraph.Walk.edges_transfer] at hkl
            exact (hMF v c'.snd hkl) ((hFs' c'.snd).mpr hxA)
          · have hyT : T.Adj y u := by
              rcases hedgeT' c' hmem_last with hh | hh
              · rwa [SimpleGraph.mem_edgeSet] at hh
              · exact absurd (hyN.mp hh) hyA
            have hyF : s(y, u) ∉ F := fun hh => hFT' y u hh (c'.edges_subset_edgeSet hmem_last)
            have hkl := KL3 c'.snd y hxA hyT hyF (M.transfer T hMT)
            rw [SimpleGraph.Walk.edges_transfer] at hkl
            exact (hMF v c'.snd hkl) ((hFs' c'.snd).mpr hxA)
  14. A contradiction arises if c'.snd ∉ A, whether y ∈ A or y ∉ A.

    If y ∈ A, reversing M and applying KL3 symmetrically shows that M contains {v, y} ∈ F, a contradiction. If neither endpoint is in A, then both end edges of c' belong to T, so all edges of c' belong to T, yielding a cycle in T and contradicting its acyclicity.

    lines 242–270

    uses SimpleGraph.mem_edgeSet, Sym2.eq_swap, SimpleGraph.Walk.edges_reverse, SimpleGraph.Walk.edges_transfer, List.mem_singleton

        · by_cases hyA : y ∈ A
          · have hxT : T.Adj u c'.snd := by
              rcases hedgeT' c' hmem_first with hh | hh
              · rwa [SimpleGraph.mem_edgeSet] at hh
              · exact absurd ((hNleft c'.snd).mp hh) hxA
            have hxF : s(c'.snd, u) ∉ F := by
              intro hh
              exact hFT' u c'.snd (by rwa [Sym2.eq_swap] at hh) (c'.edges_subset_edgeSet hmem_first)
            have hkl := KL3 y c'.snd hyA hxT.symm hxF (M.transfer T hMT).reverse
            rw [SimpleGraph.Walk.edges_reverse, List.mem_reverse, SimpleGraph.Walk.edges_transfer] at hkl
            exact (hMF v y hkl) ((hFs' y).mpr hyA)
          · have hxT : T.Adj u c'.snd := by
              rcases hedgeT' c' hmem_first with hh | hh
              · rwa [SimpleGraph.mem_edgeSet] at hh
              · exact absurd ((hNleft c'.snd).mp hh) hxA
            have hyT : T.Adj y u := by
              rcases hedgeT' c' hmem_last with hh | hh
              · rwa [SimpleGraph.mem_edgeSet] at hh
              · exact absurd (hyN.mp hh) hyA
            have hall : ∀ e ∈ c'.edges, e ∈ T.edgeSet := by
              intro e he
              rw [hcedges] at he
              rcases List.mem_cons.mp he with rfl | he
              · exact (SimpleGraph.mem_edgeSet T).mpr hxT
              · rcases List.mem_append.mp he with he | he
                · exact hMT e he
                · rw [List.mem_singleton] at he
                  exact he ▸ (SimpleGraph.mem_edgeSet T).mpr hyT
            exact hTacyc (c'.transfer T hall) (hc'.transfer hall)
  15. If the cycle c contains no edges of N, all its edges belong to T, contradicting the acyclicity of T. automation

    Without any edges from N, every edge of c belongs to T. Transferring c into T produces a cycle in T, contradicting that T is acyclic. Hence T' has no cycles and is a tree.

    lines 271–273

    uses Or.resolve_right

      · simp only [not_exists, not_and] at hnew
        have hall : ∀ e ∈ c.edges, e ∈ T.edgeSet := fun e he => (hedgeT' c he).resolve_right (hnew e he)
        exact hTacyc (c.transfer T hall) (hc.transfer hall)
op223_gts_is_tree_sym2_mem
An unordered pair s(a, b) belongs to {e | ∃ z, e = s(x, z) ∧ P z} if and only if (a = x ∧ P b) ∨ (b = x ∧ P a).
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.
Or.inl
From a proof of A, infer A ∨ B.
Or.inr
From a proof of B, infer A ∨ B.
Sym2.eq_swap
An unordered pair is symmetric: s(a, b) = s(b, a).
SimpleGraph.irrefl
No vertex in a simple graph is adjacent to itself.
SimpleGraph.edgeSet_sup
The edge set of the union of two graphs is the union of their edge sets.
SimpleGraph.edgeSet_deleteEdges
Deleting an edge set from a graph removes those edges from its edge set.
SimpleGraph.edgeSet_fromEdgeSet
The edge set of the graph from an edge set s consists of the non-loop pairs in s.
SimpleGraph.sup_adj
Two vertices are adjacent in a union of graphs if and only if they are adjacent in either graph.
SimpleGraph.deleteEdges_adj
Two vertices are adjacent in G.deleteEdges s if and only if they are adjacent in G and their edge is not in s.
SimpleGraph.fromEdgeSet_adj
Two vertices are adjacent in SimpleGraph.fromEdgeSet s if and only if their edge belongs to s and they are distinct.
SimpleGraph.Walk.snd_mem_support_of_mem_edges
If an edge s(t, u) is in the edge list of a walk, then u is in the vertex support of the walk.
SimpleGraph.reachable_iff_reflTransGen
Reachability in a graph is equivalent to the reflexive-transitive closure of the adjacency relation.
SimpleGraph.Reachable.rfl
Every vertex is reachable from itself.
SimpleGraph.connected_iff
A graph is connected if and only if it is preconnected and its vertex type is nonempty.
SimpleGraph.reachable_deleteEdges_iff_exists_walk
Two vertices are reachable after deleting an edge if and only if there exists a walk between them in the original graph avoiding that edge.
SimpleGraph.Walk.fst_mem_support_of_mem_edges
If an edge s(t, u) is in the edge list of a walk, then t is in the vertex support of the walk.
SimpleGraph.Walk.not_nil_iff_lt_length
A walk is non-nil if and only if its length is strictly positive.
SimpleGraph.Walk.length_tail
The length of the tail of a walk is the original length minus one.
SimpleGraph.Walk.support_dropLast
Dropping the last step of a non-nil walk drops the last vertex from its support list.
SimpleGraph.Walk.support_tail_of_not_nil
The vertex support of the tail of a non-nil walk is the tail of the original walk's support.
SimpleGraph.Walk.dropLast_support_concat
Concatenating the destination vertex to the dropLast support of a walk reconstructs its full support list.
SimpleGraph.Walk.cons_tail_eq
Prepending the initial step to the tail of a non-nil walk reconstructs the original walk.
SimpleGraph.Walk.concat_dropLast
Appending the final step to the dropLast walk reconstructs the original walk.
SimpleGraph.Walk.adj_penultimate
The penultimate vertex of a non-nil walk is adjacent to the walk's end vertex.
SimpleGraph.Walk.edges_concat
Appending an edge to a walk appends that edge to its edge list.
List.concat_eq_append
List concat is equivalent to appending a singleton list.
List.mem_cons_of_mem
If an element belongs to a list, it belongs to any list with an element prepended.
List.mem_append_right
If an element belongs to the second list, it belongs to the concatenation of two lists.
List.mem_cons_self
The head of a list belongs to the list.
List.nodup_cons
A cons list has no duplicates if and only if the head is not in the tail and the tail has no duplicates.
SimpleGraph.Walk.edges_transfer
Transferring a walk to a subgraph preserves its list of edges.
SimpleGraph.mem_edgeSet
An unordered pair belongs to the edge set of a graph if and only if its endpoints are adjacent.
SimpleGraph.Walk.edges_reverse
The edge list of the reverse walk is the reverse of the edge list of the walk.
List.mem_singleton
An element belongs to a singleton list [b] if and only if it equals b.
Or.resolve_right
From A ∨ B and ¬B, infer A.
Set.mem_ofPred_eq
An element belongs to a set comprehension {y | p y} if and only if it satisfies p.

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 op223_gts_is_tree_sym2_mem {V : Type*} {x : V} (P : V → Prop) (a b : V) :    s(a, b) ∈ {e : Sym2 V | ∃ z, e = s(x, z) ∧ P z} ↔ (a = x ∧ P b) ∨ (b = x ∧ P a) := by  simp only [Set.mem_ofPred_eq]  constructor  · rintro ⟨z, he, hP⟩    rw [Sym2.eq_iff] at he    rcases he with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩    · exact Or.inl ⟨rfl, hP⟩    · exact Or.inr ⟨rfl, hP⟩  · rintro (⟨rfl, hP⟩ | ⟨rfl, hP⟩)    · exact ⟨b, rfl, hP⟩    · exact ⟨a, Sym2.eq_swap, hP⟩/-- A generalized tree shift applied to a tree yields another tree. -/theorem op223_gts_is_tree {V : Type*} (T T' : SimpleGraph V)    (h : is_generalized_tree_shift T T') :    T'.IsTree := by  classical  obtain ⟨hT, u, v, p, hp, huv, hdeg, hTeq⟩ := h  set w : V := p.penultimate with hw  set A : Set V := {z | T.Adj v z ∧ z ≠ w} with hA  set F : Set (Sym2 V) := {e | ∃ z, e = s(v, z) ∧ T.Adj v z ∧ z ≠ w} with hF  set N : Set (Sym2 V) := {e | ∃ z, e = s(u, z) ∧ T.Adj v z ∧ z ≠ w} with hN  have hT'eq : T' = T.deleteEdges F ⊔ SimpleGraph.fromEdgeSet N := hTeq  have hTacyc : T.IsAcyclic := hT.isAcyclic  have huA : u ∉ A := by    simp only [hA, Set.mem_ofPred_eq]    rintro ⟨hadj, hne⟩    exact hne (hTacyc.eq_penultimate_of_adj_end hp hadj p.start_mem_support)  have hvA : v ∉ A := by    simp only [hA, Set.mem_ofPred_eq]    exact fun h => SimpleGraph.irrefl T h.1  have hFs : ∀ a b : V, s(a,b) ∈ F ↔ (a = v ∧ b ∈ A) ∨ (b = v ∧ a ∈ A) := by    intro a b    rw [hF, hA]    exact op223_gts_is_tree_sym2_mem (fun z => T.Adj v z ∧ z ≠ w) a b  have hNs : ∀ a b : V, s(a,b) ∈ N ↔ (a = u ∧ b ∈ A) ∨ (b = u ∧ a ∈ A) := by    intro a b    rw [hN, hA]    exact op223_gts_is_tree_sym2_mem (fun z => T.Adj v z ∧ z ≠ w) a b  have hFN : ∀ a b : V, s(a,b) ∈ F → s(a,b) ∈ N → False := by    intro a b hf hn    rw [hFs] at hf    rw [hNs] at hn    rcases hf with ⟨rfl, hbA⟩ | ⟨rfl, haA⟩    · rcases hn with ⟨ha, -⟩ | ⟨hb, -⟩      · exact huv ha.symm      · rw [hb] at hbA; exact huA hbA    · rcases hn with ⟨ha, -⟩ | ⟨hb, -⟩      · rw [ha] at haA; exact huA haA      · exact huv hb.symm  have hFT' : ∀ a b : V, s(a,b) ∈ F → s(a,b) ∉ T'.edgeSet := by    intro a b habF habT'    rw [hT'eq, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges,      SimpleGraph.edgeSet_fromEdgeSet] at habT'    rcases habT' with ⟨-, h2⟩ | ⟨h2, -⟩    · exact h2 habF    · exact hFN a b habF h2  have hT'adj : ∀ a b : V, T'.Adj a b ↔ (T.Adj a b ∧ s(a,b) ∉ F) ∨ s(a,b) ∈ N := by    intro a b    rw [hT'eq, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj]    constructor    · rintro (⟨h1, h2⟩ | ⟨h1, h2⟩)      · exact Or.inl ⟨h1, h2⟩      · exact Or.inr h1    · rintro (⟨h1, h2⟩ | h1)      · exact Or.inl ⟨h1, h2⟩      · have hd : a ≠ b := by          rintro rfl          rw [hNs] at h1          rcases h1 with ⟨h1, h2⟩ | ⟨h1, h2⟩          · rw [h1] at h2; exact huA h2          · rw [h1] at h2; exact huA h2        exact Or.inr ⟨h1, hd⟩  have hpF : ∀ e ∈ p.edges, e ∉ F := by    intro e he heF    rw [hF] at heF    obtain ⟨z, rfl, hzv, hzw⟩ := heF    exact hzw (hTacyc.eq_penultimate_of_adj_end hp hzv      (SimpleGraph.Walk.snd_mem_support_of_mem_edges p he))  have hpT' : ∀ e ∈ p.edges, e ∈ T'.edgeSet := by    intro e he    rw [hT'eq, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges,      SimpleGraph.edgeSet_fromEdgeSet]    exact Or.inl ⟨p.edges_subset_edgeSet he, hpF e he⟩  have hpwalk : T'.Walk u v := p.transfer T' hpT'  have hpReach : T'.Reachable v u := ⟨hpwalk.reverse⟩  have hstep : ∀ a b : V, T.Adj a b → T'.Reachable a b := by    intro a b hab    by_cases hFab : s(a,b) ∈ F    · rw [hFs] at hFab      rcases hFab with ⟨rfl, hbA⟩ | ⟨rfl, haA⟩      · exact hpReach.trans ((hT'adj u b).mpr (Or.inr ((hNs u b).mpr (Or.inl ⟨rfl, hbA⟩)))).reachable      · exact (hpReach.trans ((hT'adj u a).mpr (Or.inr ((hNs u a).mpr (Or.inl ⟨rfl, haA⟩)))).reachable).symm    · exact ((hT'adj a b).mpr (Or.inl ⟨hab, hFab⟩)).reachable  have hpre : T'.Preconnected := by    intro a b    have hab : T.Reachable a b := hT.connected.preconnected a b    rw [SimpleGraph.reachable_iff_reflTransGen] at hab    induction hab with    | refl => exact SimpleGraph.Reachable.rfl    | tail _ hbc ih => exact ih.trans (hstep _ _ hbc)  have hconn : T'.Connected := (SimpleGraph.connected_iff T').mpr ⟨hpre, hT.connected.nonempty⟩  have hbridgeA : ∀ z ∈ A, ¬ (T.deleteEdges {s(v,z)}).Reachable v z := by    intro z hz    have hb : T.IsBridge s(v, z) := SimpleGraph.isAcyclic_iff_forall_adj_isBridge.mp hTacyc hz.1    exact SimpleGraph.isBridge_iff.mp hb  have hptrans : ∀ z ∈ A, (T.deleteEdges {s(v,z)}).Walk u v := by    intro z hz    refine p.transfer _ (fun e he => ?_)    rw [SimpleGraph.edgeSet_deleteEdges]    refine ⟨p.edges_subset_edgeSet he, ?_⟩    simp only [Set.mem_singleton_iff]    intro hh    exact hpF e he (hh ▸ ((hFs v z).mpr (Or.inl ⟨rfl, hz⟩)))  have hFs' : ∀ z : V, s(v,z) ∈ F ↔ z ∈ A := by    intro z    rw [hFs]    exact ⟨fun h => h.elim (fun h => h.2) (fun h => absurd h.2 hvA), fun h => Or.inl ⟨rfl, h⟩⟩  have hNleft : ∀ z : V, s(u,z) ∈ N ↔ z ∈ A := by    intro z    rw [hNs]    exact ⟨fun h => h.elim (fun h => h.2) (fun h => absurd h.2 huA), fun h => Or.inl ⟨rfl, h⟩⟩  have KL2 : ∀ z₁ z₂ : V, z₁ ∈ A → z₂ ∈ A → z₁ ≠ z₂ →      ∀ W : T.Walk z₁ z₂, s(v,z₁) ∈ W.edges := by    intro z₁ z₂ h1 h2 hne W    by_contra hcon    apply hbridgeA z₁ h1    have hW1 : (T.deleteEdges {s(v,z₁)}).Reachable z₁ z₂ := by      rw [SimpleGraph.reachable_deleteEdges_iff_exists_walk]      exact ⟨W, hcon⟩    have hW2 : (T.deleteEdges {s(v,z₁)}).Reachable z₂ v := by      have hadj : (T.deleteEdges {s(v,z₁)}).Adj z₂ v := by        rw [SimpleGraph.deleteEdges_adj]        refine ⟨h2.1.symm, ?_⟩        simp only [Set.mem_singleton_iff]        intro hh        rw [Sym2.eq_iff] at hh        rcases hh with ⟨-, h'⟩ | ⟨h', -⟩        · exact SimpleGraph.irrefl T (h' ▸ h1.1)        · exact hne h'.symm      exact hadj.reachable    exact (hW1.trans hW2).symm  have KL3 : ∀ z y : V, z ∈ A → T.Adj y u → s(y,u) ∉ F →      ∀ W : T.Walk z y, s(v,z) ∈ W.edges := by    intro z y hz hadj hnotF W    by_contra hcon    apply hbridgeA z hz    have hW1 : (T.deleteEdges {s(v,z)}).Reachable z y := by      rw [SimpleGraph.reachable_deleteEdges_iff_exists_walk]      exact ⟨W, hcon⟩    have hW2 : (T.deleteEdges {s(v,z)}).Reachable y v := by      have hadj' : (T.deleteEdges {s(v,z)}).Adj y u := by        rw [SimpleGraph.deleteEdges_adj]        refine ⟨hadj, ?_⟩        simp only [Set.mem_singleton_iff]        intro hh        exact hnotF (hh ▸ ((hFs v z).mpr (Or.inl ⟨rfl, hz⟩)))      exact hadj'.reachable.trans ⟨hptrans z hz⟩    exact (hW1.trans hW2).symm  refine ⟨hconn, ?_⟩  intro x₀ c hc  have hedgeT' : ∀ {a b : V} (W : T'.Walk a b) ⦃e : Sym2 V⦄, e ∈ W.edges →      e ∈ T.edgeSet ∨ e ∈ N := by    intro a b W e he    have h1 : e ∈ T'.edgeSet := W.edges_subset_edgeSet he    rw [hT'eq, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges,      SimpleGraph.edgeSet_fromEdgeSet] at h1    rcases h1 with ⟨hh, -⟩ | ⟨hh, -⟩    · exact Or.inl hh    · exact Or.inr hh  by_cases hnew : ∃ e ∈ c.edges, e ∈ N  · obtain ⟨e₀, he₀, he₀N⟩ := hnew    have husupp : u ∈ c.support := by      rw [hN] at he₀N      obtain ⟨z, rfl, -⟩ := he₀N      exact SimpleGraph.Walk.fst_mem_support_of_mem_edges c he₀    set c' : T'.Walk u u := c.rotate u husupp with hc'def    have hc' : c'.IsCycle := hc.rotate husupp    have hlen : 3 ≤ c'.length := hc'.isCircuit.three_le_length    have htnn : ¬ c'.tail.Nil := by      rw [SimpleGraph.Walk.not_nil_iff_lt_length, SimpleGraph.Walk.length_tail]; omega    set y : V := (c'.tail).penultimate with hy    let M : T'.Walk c'.snd y := (c'.tail).dropLast    have hMsupp : M.support = (c'.tail.support).dropLast :=      SimpleGraph.Walk.support_dropLast htnn    have htnod : (c'.tail.support).Nodup := by      rw [SimpleGraph.Walk.support_tail_of_not_nil c' hc'.not_nil]      exact hc'.support_nodup    have huM : u ∉ M.support := by      rw [hMsupp]      have hl : (c'.tail.support).dropLast ++ [u] = c'.tail.support :=        SimpleGraph.Walk.dropLast_support_concat c'.tail      have hnod : ((c'.tail.support).dropLast ++ [u]).Nodup := by rw [hl]; exact htnod      intro hmem      exact (List.nodup_append.mp hnod).2.2 u hmem u (by simp) rfl    have hMT : ∀ e ∈ M.edges, e ∈ T.edgeSet := by      intro e he      rcases hedgeT' M he with hh | hh      · exact hh      · rw [hN] at hh        obtain ⟨z, rfl, -⟩ := hh        exact absurd (SimpleGraph.Walk.fst_mem_support_of_mem_edges M he) huM    have hMF : ∀ a b : V, s(a,b) ∈ M.edges → s(a,b) ∉ F := by      intro a b he      exact fun hF' => hFT' a b hF' (M.edges_subset_edgeSet he)    have hcedges1 : c'.edges = s(u, c'.snd) :: c'.tail.edges := by      nth_rewrite 1 [← SimpleGraph.Walk.cons_tail_eq c' hc'.not_nil]      simp [SimpleGraph.Walk.edges_cons]    have hcedges2 : c'.tail.edges = M.edges ++ [s(y, u)] := by      conv_lhs => rw [← SimpleGraph.Walk.concat_dropLast (p := c'.tail) (SimpleGraph.Walk.adj_penultimate htnn)]      rw [SimpleGraph.Walk.edges_concat, List.concat_eq_append]    have hcedges : c'.edges = s(u, c'.snd) :: (M.edges ++ [s(y, u)]) := by      rw [hcedges1, hcedges2]    have hyN : s(y, u) ∈ N ↔ y ∈ A := by      rw [hNs]      exact ⟨fun h => h.elim (fun h => h.1 ▸ h.2) (fun h => h.2), fun h => Or.inr ⟨rfl, h⟩⟩    have hmem_last : s(y, u) ∈ c'.edges := by      rw [hcedges]      exact List.mem_cons_of_mem _ (List.mem_append_right _ (List.mem_singleton.mpr rfl))    have hmem_first : s(u, c'.snd) ∈ c'.edges := by      rw [hcedges]; exact List.mem_cons_self ..    by_cases hxA : c'.snd ∈ A    · by_cases hyA : y ∈ A      · have hxy : c'.snd ≠ y := by          intro hxy'          have hnod := hc'.isCircuit.isTrail.edges_nodup          rw [hcedges] at hnod          rw [List.nodup_cons] at hnod          exact hnod.1 (List.mem_append_right _ (List.mem_singleton.mpr (by rw [hxy']; exact Sym2.eq_swap.symm)))        have hkl := KL2 c'.snd y hxA hyA hxy (M.transfer T hMT)        rw [SimpleGraph.Walk.edges_transfer] at hkl        exact (hMF v c'.snd hkl) ((hFs' c'.snd).mpr hxA)      · have hyT : T.Adj y u := by          rcases hedgeT' c' hmem_last with hh | hh          · rwa [SimpleGraph.mem_edgeSet] at hh          · exact absurd (hyN.mp hh) hyA        have hyF : s(y, u) ∉ F := fun hh => hFT' y u hh (c'.edges_subset_edgeSet hmem_last)        have hkl := KL3 c'.snd y hxA hyT hyF (M.transfer T hMT)        rw [SimpleGraph.Walk.edges_transfer] at hkl        exact (hMF v c'.snd hkl) ((hFs' c'.snd).mpr hxA)    · by_cases hyA : y ∈ A      · have hxT : T.Adj u c'.snd := by          rcases hedgeT' c' hmem_first with hh | hh          · rwa [SimpleGraph.mem_edgeSet] at hh          · exact absurd ((hNleft c'.snd).mp hh) hxA        have hxF : s(c'.snd, u) ∉ F := by          intro hh          exact hFT' u c'.snd (by rwa [Sym2.eq_swap] at hh) (c'.edges_subset_edgeSet hmem_first)        have hkl := KL3 y c'.snd hyA hxT.symm hxF (M.transfer T hMT).reverse        rw [SimpleGraph.Walk.edges_reverse, List.mem_reverse, SimpleGraph.Walk.edges_transfer] at hkl        exact (hMF v y hkl) ((hFs' y).mpr hyA)      · have hxT : T.Adj u c'.snd := by          rcases hedgeT' c' hmem_first with hh | hh          · rwa [SimpleGraph.mem_edgeSet] at hh          · exact absurd ((hNleft c'.snd).mp hh) hxA        have hyT : T.Adj y u := by          rcases hedgeT' c' hmem_last with hh | hh          · rwa [SimpleGraph.mem_edgeSet] at hh          · exact absurd (hyN.mp hh) hyA        have hall : ∀ e ∈ c'.edges, e ∈ T.edgeSet := by          intro e he          rw [hcedges] at he          rcases List.mem_cons.mp he with rfl | he          · exact (SimpleGraph.mem_edgeSet T).mpr hxT          · rcases List.mem_append.mp he with he | he            · exact hMT e he            · rw [List.mem_singleton] at he              exact he ▸ (SimpleGraph.mem_edgeSet T).mpr hyT        exact hTacyc (c'.transfer T hall) (hc'.transfer hall)  · simp only [not_exists, not_and] at hnew    have hall : ∀ e ∈ c.edges, e ∈ T.edgeSet := fun e he => (hedgeT' c he).resolve_right (hnew e he)    exact hTacyc (c.transfer T hall) (hc.transfer hall)
See it in the graphDiscuss this resultChallenge it