AFTD Auto-Formalizing Theoretical Domains

mst_id_certificate_imp_minor_edges_loop_or_bridge

theoremverifiedformalization

If a partial realization β is an MST identification certificate for a connected simple graph G on a finite vertex set, then every unqueried edge of G is either a loop or a bridge in the minor G_β.

Statement

open scoped Classical in
theorem mst_id_certificate_imp_minor_edges_loop_or_bridge {V : Type*} [Fintype V]
    (G : SimpleGraph V) (hG : G.Connected) (β : G.edgeSet → Option Bool)
    (hcert : is_mst_certificate G β) :
    ∀ (e : G.edgeSet), β e = none →
      minor_edge_is_loop G β e ∨ minor_edge_is_bridge G β e
Formalizes
arXiv:2610.40844 Lemma 2.2
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • minor_edge_is_loopFor a simple graph G and a partial edge-weight realization β : G.edgeSet → Option Bool, an edge e of G is a loop in the minor G_β…
  • minor_edge_is_bridgeFor a simple graph G and a partial edge-weight realization β : G.edgeSet → Option Bool, an edge e of G is a bridge in the minor G_β if it…
  • is_mst_certificateA partial realization β : G.edgeSet → Option Bool is an MST identification certificate for G if there exists a spanning tree T of G (T ≤ G…
  • is_mst_forA simple graph T on a finite vertex type V is a minimum spanning tree of G under edge realization α : G.edgeSet → Bool if T is a subgraph…
  • 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.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

Read back from the Lean

Let $V$ be a finite type, and let $G$ be a connected simple graph on $V$. Let $\beta : E(G) \to \mathrm{Option}\,\mathrm{Bool}$ be a partial assignment of boolean values to the edges of $G$. Assume $\beta$ is an MST certificate for $G$ (that is, there exists a spanning tree $T \le G$ such that for every total assignment $\alpha : E(G) \to \mathrm{Bool}$ agreeing with $\beta$ wherever $\beta$ is defined, $T$ is a minimum spanning tree of $G$ with edge weights given by $\alpha$, where $\mathrm{true}$ has weight 1 and $\mathrm{false}$ has weight 0). Then, for every edge $e \in E(G)$ on which $\beta$ is undefined ($\beta(e) = \mathrm{none}$), at least one of the following holds: 1. $e$ is a loop in the minor: the endpoints of $e$ are reachable from each other in the subgraph formed by the edges assigned $\mathrm{some}\;\mathrm{false}$ by $\beta$. 2. $e$ is a bridge in the minor: the endpoints of $e$ are not reachable from each other via edges assigned $\mathrm{some}\;\mathrm{false}$, and they are not reachable from each other in $G$ after deleting $e$ and all edges assigned $\mathrm{some}\;\mathrm{true}$.

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

To certify a minimum spanning tree, a partial realization β of edge weights must identify a spanning tree T that remains optimal under every completion of β to {0, 1}. For any unqueried edge e = {a, b}, if e is neither a loop nor a bridge in the minor G_β, then a and b are connected by a walk in G avoiding e and all weight-1 edges. If e belongs to T, this walk crosses the fundamental cut of e in T at some edge d ∉ T, allowing an edge swap that strictly reduces the cost of T under a valid completion; if e does not belong to T, the path in T between a and b contains a weight-1 edge f, and swapping f for e likewise yields a strictly cheaper spanning tree, in both cases contradicting the optimality of T.

  1. The cost mstid_cost G α S equals the number of edges of G in S with weight 1 (α e = true).

    The definition of mstid_cost sums over all edges e of G an indicator that equals 1 when e ∈ S and α(e) = true, and 0 otherwise. By rewriting the nested if-then-else conditions into a single conjunction and applying Finset.card_filter, this sum equals the cardinality of the filtered edge set.

    lines 11–18

    uses Finset.sum_congr, Finset.card_filter

      classical
      have h1 : mstid_cost G α S = ∑ e : G.edgeSet,
          (if ((e : Sym2 V) ∈ S.edgeSet ∧ α e = true) then (1:ℕ) else 0) := by
        refine Finset.sum_congr rfl ?_
        intro e _
        by_cases h : (e : Sym2 V) ∈ S.edgeSet <;> by_cases hb : α e <;> simp [h, hb]
      rw [h1, ← Finset.card_filter]
    
  2. Replacing an edge remG of weight 1 with an edge addG of weight 0 in T to form S decreases the cost by exactly 1.

    By mstid_cost_eq_card, the costs of S and T are the cardinalities of their weight-1 edge sets. Since S is obtained from T by removing remG and adding addG where α(addG) = false, the weight-1 edges of S are precisely those of T with remG erased. Because remG ∈ T has α(remG) = true, erasing it reduces the cardinality by 1 by Finset.card_erase_of_mem.

    lines 19–49

    uses mstid_cost_eq_card, Subtype.ext, Bool.noConfusion, Finset.card_erase_of_mem

    private lemma mstid_cost_swap {V : Type*} [Fintype V] (G T S : SimpleGraph V)
        (α : G.edgeSet → Bool) (remG addG : G.edgeSet)
        (hS : S.edgeSet = insert (addG : Sym2 V) (T.edgeSet \ {(remG : Sym2 V)}))
        (hrem : (remG : Sym2 V) ∈ T.edgeSet)
        (hαrem : α remG = true) (hαadd : α addG = false) :
        mstid_cost G α S = mstid_cost G α T - 1 := by
      classical
      rw [mstid_cost_eq_card, mstid_cost_eq_card]
      have hfil : ((Finset.univ : Finset G.edgeSet).filter
            (fun e : G.edgeSet => (e : Sym2 V) ∈ S.edgeSet ∧ α e = true)) =
          (((Finset.univ : Finset G.edgeSet).filter
            (fun e : G.edgeSet => (e : Sym2 V) ∈ T.edgeSet ∧ α e = true)).erase remG) := by
        ext x
        simp only [Finset.mem_filter, Finset.mem_univ, Finset.mem_erase, true_and]
        constructor
        · rintro ⟨hmem, hαx⟩
          rw [hS] at hmem
          rcases hmem with hx | ⟨hxt, hxne⟩
          · exfalso
            have hx' : x = addG := Subtype.ext hx
            rw [hx'] at hαx
            rw [hαx] at hαadd
            exact Bool.noConfusion hαadd
          · exact ⟨fun h => hxne (congrArg Subtype.val h), hxt, hαx⟩
        · rintro ⟨hxne, hxt, hαx⟩
          refine ⟨?_, hαx⟩
          rw [hS]
          exact Or.inr ⟨hxt, fun h => hxne (Subtype.ext h)⟩
      rw [hfil, Finset.card_erase_of_mem]
      simp [hrem, hαrem]
    
  3. For distinct vertices a ≠ b, the edge set of (T \ {e}) ⊔ edge(a, b) equals insert s(a, b) (T.edgeSet \ {e}).

    Because a ≠ b, the pair s(a, b) is not a self-loop (not on the diagonal). Thus the edge set of the single edge between a and b is simply {s(a, b)}. Unfolding the edge sets of the graph supremum and deletion and rewriting the union gives the inserted set.

    lines 50–62

    uses Set.mem_sdiff, Set.mem_singleton_iff, And.left, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges, SimpleGraph.edgeSet_edge, Set.union_comm, Set.singleton_union

    private lemma mstid_swap_edges {V : Type*} (T : SimpleGraph V) {e : Sym2 V} {a b : V}
        (hab : a ≠ b) :
        (T.deleteEdges {e} ⊔ SimpleGraph.edge a b).edgeSet =
          insert s(a, b) (T.edgeSet \ {e}) := by
      classical
      have hdiag : s(a, b) ∉ Sym2.diagSet := by simpa using hab
      have hsing : ({s(a, b)} : Set (Sym2 V)) \ Sym2.diagSet = {s(a, b)} := by
        ext x
        simp only [Set.mem_sdiff, Set.mem_singleton_iff]
        exact ⟨And.left, fun hx => ⟨hx, fun hx' => hdiag (hx ▸ hx')⟩⟩
      rw [SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges, SimpleGraph.edgeSet_edge,
        hsing, Set.union_comm, Set.singleton_union]
    
  4. If T is a tree, e ∈ T, a ≠ b, s(a, b) ∉ T, and a, b are not reachable in T \ {e}, then (T \ {e}) ⊔ edge(a, b) is also a tree.

    The deleted graph T \ {e} is acyclic as a subgraph of T, and adding the edge between unreachable vertices a and b preserves acyclicity. Furthermore, by is_tree_iff_is_acyclic_and_card, a graph on a finite vertex set is a tree if and only if it is acyclic and has |V| - 1 edges. Since one edge was removed and one edge was added, the edge count is preserved, so the new graph is a tree.

    lines 63–82

    uses SimpleGraph.deleteEdges_le, mstid_swap_edges, is_tree_iff_is_acyclic_and_card, Set.ncard_insert_of_notMem, Set.ncard_sdiff_singleton_add_one, Nat.card_coe_set_eq

    private lemma mstid_swap_isTree
        {V : Type*} [Fintype V] (T : SimpleGraph V) (hT : T.IsTree)
        {e : Sym2 V} (he : e ∈ T.edgeSet) {a b : V} (hab : a ≠ b) (hne : s(a, b) ∉ T.edgeSet)
        (hnr : ¬ (T.deleteEdges {e}).Reachable a b) :
        (T.deleteEdges {e} ⊔ SimpleGraph.edge a b).IsTree := by
      classical
      have hacyc : (T.deleteEdges {e}).IsAcyclic := hT.isAcyclic.anti (SimpleGraph.deleteEdges_le _)
      have hSacyc : (T.deleteEdges {e} ⊔ SimpleGraph.edge a b).IsAcyclic :=
        hacyc.sup_edge_of_not_reachable hnr
      have h_edges := mstid_swap_edges (T := T) (e := e) (a := a) (b := b) hab
      rw [is_tree_iff_is_acyclic_and_card]
      refine ⟨hSacyc, ?_⟩
      have hcardT : Nat.card T.edgeSet + 1 = Nat.card V :=
        (is_tree_iff_is_acyclic_and_card T).mp hT |>.2
      have key : ((T.deleteEdges {e} ⊔ SimpleGraph.edge a b).edgeSet).ncard = T.edgeSet.ncard := by
        rw [h_edges, Set.ncard_insert_of_notMem (fun h => hne h.1)]
        exact Set.ncard_sdiff_singleton_add_one he
      rw [Nat.card_coe_set_eq, key, ← Nat.card_coe_set_eq]
      exact hcardT
    
  5. In a tree T, deleting any edge f on a simple path q between u and v disconnects u and v.

    Reachability in T \ {f} is equivalent to the existence of a walk in T avoiding f. If such a walk existed, its reduction to a path would yield a simple path in T between u and v avoiding f. But paths in a tree are unique, so this path must equal q, which contains f, a contradiction.

    lines 83–97

    uses Sym2.ind, SimpleGraph.reachable_deleteEdges_iff_exists_walk, SimpleGraph.Walk.edges_toPath_subset_edges

    private lemma mstid_path_edge_not_reachable {V : Type*} (T : SimpleGraph V) (hT : T.IsTree)
        {u v : V} (q : T.Walk u v) (hq : q.IsPath) {f : Sym2 V} (hf : f ∈ q.edges) :
        ¬ (T.deleteEdges {f}).Reachable u v := by
      classical
      have key : ∀ f : Sym2 V,
          ((T.deleteEdges {f}).Reachable u v ↔ ∃ p : T.Walk u v, f ∉ p.edges) :=
        fun f => @Sym2.ind V
          (fun g => ((T.deleteEdges {g}).Reachable u v ↔ ∃ p : T.Walk u v, g ∉ p.edges))
          (fun a b => SimpleGraph.reachable_deleteEdges_iff_exists_walk) f
      intro h
      rw [key f] at h
      obtain ⟨p, hp⟩ := h
      have huniq : (↑p.toPath : T.Walk u v) = q := (hT.existsUnique_path u v).unique p.toPath.isPath hq
      exact hp (SimpleGraph.Walk.edges_toPath_subset_edges p (huniq ▸ hf))
    
  6. Swapping an edge of weight 1 for an edge of weight 0 in a minimum spanning tree derives a contradiction.

    Because T is an MST for α and S is a spanning tree, cost(T) ≤ cost(S). But by mstid_cost_swap, cost(S) = cost(T) - 1, and since remG ∈ T has weight 1, cost(T) ≥ 1. This gives cost(T) ≤ cost(T) - 1, which omega refutes.

    lines 98–114

    uses mstid_cost_swap, mstid_cost_eq_card, Finset.card_pos

    private lemma mstid_improve {V : Type*} [Fintype V] (G T S : SimpleGraph V)
        (α : G.edgeSet → Bool) (remG addG : G.edgeSet)
        (hSG : S ≤ G) (hS : S.IsTree) (hmin : is_mst_for G T α)
        (hSed : S.edgeSet = insert (addG : Sym2 V) (T.edgeSet \ {(remG : Sym2 V)}))
        (hrem : (remG : Sym2 V) ∈ T.edgeSet)
        (hαrem : α remG = true) (hαadd : α addG = false) : False := by
      have h1 : mstid_cost G α T ≤ mstid_cost G α S := hmin.2.2 S hSG hS
      have h2 : mstid_cost G α S = mstid_cost G α T - 1 :=
        mstid_cost_swap G T S α remG addG hSed hrem hαrem hαadd
      have hpos : 1 ≤ mstid_cost G α T := by
        rw [mstid_cost_eq_card]
        have hmem : remG ∈ ((Finset.univ : Finset G.edgeSet).filter
            (fun e : G.edgeSet => (e : Sym2 V) ∈ T.edgeSet ∧ α e = true)) := by
          simp [hrem, hαrem]
        exact Finset.card_pos.mpr ⟨remG, hmem⟩
      omega
    
  7. An edge assignment α setting weight 0 on Z ∪ {addG} and weight 1 elsewhere is consistent with β, assigns 1 to remG, and assigns 0 to addG.

    For any queried edge x, if x ∈ Z ∪ {addG}, it cannot have β(x) = some true by hypothesis, so β(x) = some false and α(x) = false. If x ∉ Z ∪ {addG}, it cannot have β(x) = some false, so β(x) = some true and α(x) = true. Since remG is neither in Z nor equal to addG, α(remG) = true, and α(addG) = false.

    lines 115–141

    uses if_pos, Option.some.inj, if_neg, Or.inl, Or.inr

    private lemma mstid_alpha_lemmas {V : Type*} (G : SimpleGraph V)
        (β : G.edgeSet → Option Bool) (Z : Set (Sym2 V))
        (hZmem : ∀ x : G.edgeSet, ((x : Sym2 V) ∈ Z ↔ β x = some false))
        (remG addG : Sym2 V) (hneZ : remG ∉ Z) (hneadd : remG ≠ addG)
        (hDadd : ∀ x : G.edgeSet, β x = some true → (x : Sym2 V) ≠ addG) :
        (∀ (x : G.edgeSet) (b : Bool), β x = some b →
          (if (x : Sym2 V) ∈ Z ∨ (x : Sym2 V) = addG then false else true) = b) ∧
        ((if remG ∈ Z ∨ remG = addG then false else true) = true) ∧
        ((if addG ∈ Z ∨ addG = addG then false else true) = false) := by
      refine ⟨?_, ?_, ?_⟩
      · intro x b hb
        by_cases h : (x : Sym2 V) ∈ Z ∨ (x : Sym2 V) = addG
        · rw [if_pos h]
          rcases h with h1 | h2
          · rw [(hZmem x).mp h1] at hb
            rw [Option.some.inj hb]
          · rcases b with _ | _
            · rfl
            · exact absurd hb (hDadd x · h2)
        · rw [if_neg h]
          rcases b with _ | _
          · exact absurd ((hZmem x).mpr hb) (fun hc => h (Or.inl hc))
          · rfl
      · rw [if_neg]
        exact fun hc => hc.elim hneZ hneadd
      · rw [if_pos (Or.inr rfl)]
    
  8. If T ≤ G and add ∈ G.edgeSet, then (T \ {rem}) ∪ {add} is a subgraph of G.

    Any edge in the swapped graph is either add, which is in G by assumption, or an edge from T \ {rem} ⊆ T ⊆ G by monotonicity of edge sets.

    lines 142–151

    uses SimpleGraph.edgeSet_mono

    private lemma mstid_subset_G {V : Type*} (G T : SimpleGraph V) (hTG : T ≤ G)
        {rem add : Sym2 V} (haddG : add ∈ G.edgeSet)
        {S : SimpleGraph V} (hS : S.edgeSet = insert add (T.edgeSet \ {rem})) : S ≤ G := by
      intro x y hxy
      have hx : s(x, y) ∈ S.edgeSet := hxy
      rw [hS] at hx
      rcases hx with rfl | ⟨hx, _⟩
      · exact haddG
      · exact SimpleGraph.edgeSet_mono hTG hx
    
  9. Unpack the certificate to obtain the tree T, and define the contracted edge set Z and deleted edge set D.

    From the hypothesis that β certifies an MST, obtain a spanning tree T ≤ G that is an MST for every completion α compatible with β. Define Z as the set of edges with β = some false (to be contracted in the minor) and D as the set with β = some true (to be deleted in the minor), and establish the membership equivalences hZmem and hDmem.

    lines 152–176

    uses Subtype.ext

    open scoped Classical in
    /-- If β certifies an MST, then every unqueried edge in the minor is a loop or bridge. -/
    theorem mst_id_certificate_imp_minor_edges_loop_or_bridge {V : Type*} [Fintype V]
        (G : SimpleGraph V) (hG : G.Connected) (β : G.edgeSet → Option Bool)
        (hcert : is_mst_certificate G β) :
        ∀ (e : G.edgeSet), β e = none →
          minor_edge_is_loop G β e ∨ minor_edge_is_bridge G β e := by
      classical
      obtain ⟨T, hTG, hTtree, hTmin⟩ := hcert
      set Z : Set (Sym2 V) := {s | ∃ (h : s ∈ G.edgeSet), β ⟨s, h⟩ = some false} with hZdef
      set D : Set (Sym2 V) := {s | ∃ (h : s ∈ G.edgeSet), β ⟨s, h⟩ = some true} with hDdef
      have hZmem : ∀ x : G.edgeSet, ((x : Sym2 V) ∈ Z ↔ β x = some false) := by
        intro x
        refine ⟨?_, ?_⟩
        · rintro ⟨h, hb⟩
          rwa [show (⟨(x : Sym2 V), h⟩ : G.edgeSet) = x from Subtype.ext rfl] at hb
        · intro hb
          exact ⟨x.2, by rwa [show (⟨(x : Sym2 V), x.2⟩ : G.edgeSet) = x from Subtype.ext rfl]⟩
      have hDmem : ∀ x : G.edgeSet, ((x : Sym2 V) ∈ D ↔ β x = some true) := by
        intro x
        refine ⟨?_, ?_⟩
        · rintro ⟨h, hb⟩
          rwa [show (⟨(x : Sym2 V), h⟩ : G.edgeSet) = x from Subtype.ext rfl] at hb
        · intro hb
          exact ⟨x.2, by rwa [show (⟨(x : Sym2 V), x.2⟩ : G.edgeSet) = x from Subtype.ext rfl]⟩
  10. For an unqueried edge e = s(a, b), if e is not a loop in the minor, it suffices to show a and b are disconnected in G \ (D ∪ {e}).

    Assume e is not a loop in the minor, meaning a and b are not reachable via Z. By definition, e is a bridge in the minor if a and b are also not reachable in G \ (D ∪ {e}). To derive a contradiction, suppose there is a walk p connecting a and b in G \ (D ∪ {e}).

    lines 177–198

    uses Or.inl, SimpleGraph.mem_edgeSet

      have key : ∀ (a b : V) (heG : s(a, b) ∈ G.edgeSet),
          β ⟨s(a, b), heG⟩ = none →
          minor_edge_is_loop G β ⟨s(a, b), heG⟩ ∨ minor_edge_is_bridge G β ⟨s(a, b), heG⟩ := by
        intro a b heG hnone
        by_cases hloop : minor_edge_is_loop G β ⟨s(a, b), heG⟩
        · exact Or.inl hloop
        · right
          have hab : a ≠ b := (SimpleGraph.mem_edgeSet G).mp heG |>.ne
          have hnZ : ¬ (SimpleGraph.fromEdgeSet Z).Reachable a b :=
            fun h => hloop ⟨a, b, rfl, h⟩
          have hzt : s(a, b) ∉ Z := by
            intro hc
            rw [(hZmem ⟨s(a, b), heG⟩).mp hc] at hnone
            exact absurd hnone (by simp)
          have hDz : ∀ x : G.edgeSet, β x = some true → (x : Sym2 V) ≠ s(a, b) := by
            intro x hx hc
            have hxD : (x : Sym2 V) ∈ D := (hDmem x).mpr hx
            rw [hc] at hxD
            rw [(hDmem ⟨s(a, b), heG⟩).mp hxD] at hnone
            exact absurd hnone (by simp)
          refine ⟨a, b, rfl, hnZ, ?_⟩
          intro hreach
  11. If e ∈ T, swapping e for an edge d of p crossing the cut T \ {e} contradicts the optimality of T.

    Since T is a tree, e is a bridge of T. Deleting e partitions T into connected components; let S₀ be the component containing a. The walk p connects a ∈ S₀ to b ∉ S₀, so p contains a boundary dart d crossing the cut. The edge of d is in G, not in D, not equal to e, and not in T. Swapping e for d.edge yields a tree S ≤ G. Completing β with α giving weight 1 to e and weight 0 to d.edge makes S strictly cheaper than T, contradicting optimality via mstid_improve.

    lines 199–241

    uses SimpleGraph.isAcyclic_iff_forall_adj_isBridge, SimpleGraph.mem_edgeSet, SimpleGraph.Reachable.rfl, List.mem_map_of_mem, SimpleGraph.Walk.edges_subset_edgeSet, SimpleGraph.edgeSet_deleteEdges, Or.inr, SimpleGraph.deleteEdges_adj, mstid_swap_isTree, mstid_swap_edges, mstid_alpha_lemmas, Ne.symm, mstid_subset_G, mstid_improve

          by_cases hmemT : s(a, b) ∈ T.edgeSet
          · have hbridge : T.IsBridge s(a, b) :=
              SimpleGraph.isAcyclic_iff_forall_adj_isBridge.mp hTtree.isAcyclic
                ((SimpleGraph.mem_edgeSet T).mp hmemT)
            set S₀ : Set V := {v | (T.deleteEdges {s(a, b)}).Reachable a v} with hS₀
            have haS : a ∈ S₀ := SimpleGraph.Reachable.rfl
            have hbS : b ∉ S₀ := hbridge
            obtain ⟨p⟩ := hreach
            obtain ⟨d, hdmem, hdfst, hdsnd⟩ := p.exists_boundary_dart S₀ haS hbS
            have hgp : d.edge ∈ p.edges := by
              have h := List.mem_map_of_mem (f := SimpleGraph.Dart.edge) hdmem
              simpa [SimpleGraph.Walk.edges] using h
            have hgdel := SimpleGraph.Walk.edges_subset_edgeSet p hgp
            rw [SimpleGraph.edgeSet_deleteEdges] at hgdel
            have hgG : d.edge ∈ G.edgeSet := hgdel.1
            have hgnD : d.edge ∉ D := fun hc => hgdel.2 (Or.inr hc)
            have hgne : d.edge ≠ s(a, b) := fun hc => hgdel.2 (Or.inl hc)
            have huv_ne : d.toProd.1 ≠ d.toProd.2 := by
              intro hc
              exact hdsnd (hc ▸ hdfst)
            have hneT : d.edge ∉ T.edgeSet := by
              intro hT'
              have hTadj : T.Adj d.toProd.1 d.toProd.2 := (SimpleGraph.mem_edgeSet T).mp hT'
              have hadj : (T.deleteEdges {s(a, b)}).Adj d.toProd.1 d.toProd.2 := by
                rw [SimpleGraph.deleteEdges_adj]
                exact ⟨hTadj, hgne⟩
              exact hdsnd (hdfst.trans hadj.reachable)
            have hnr : ¬ (T.deleteEdges {s(a, b)}).Reachable d.toProd.1 d.toProd.2 :=
              fun hc => hdsnd (hdfst.trans hc)
            have hStree : (T.deleteEdges {s(a, b)} ⊔ SimpleGraph.edge d.toProd.1 d.toProd.2).IsTree :=
              mstid_swap_isTree (T := T) (e := s(a, b)) (a := d.toProd.1) (b := d.toProd.2)
                hTtree hmemT huv_ne hneT hnr
            have hSe : (T.deleteEdges {s(a, b)} ⊔ SimpleGraph.edge d.toProd.1 d.toProd.2).edgeSet =
                insert d.edge (T.edgeSet \ {s(a, b)}) :=
              mstid_swap_edges (T := T) (e := s(a, b)) (a := d.toProd.1) (b := d.toProd.2) huv_ne
            have hDg : ∀ x : G.edgeSet, β x = some true → (x : Sym2 V) ≠ d.edge := by
              intro x hx hc
              exact hgnD (hc ▸ ((hDmem x).mpr hx))
            have hα := mstid_alpha_lemmas G β Z hZmem s(a, b) d.edge hzt (Ne.symm hgne) hDg
            have hSG : (T.deleteEdges {s(a, b)} ⊔ SimpleGraph.edge d.toProd.1 d.toProd.2) ≤ G :=
              mstid_subset_G G T hTG hgG hSe
            exact mstid_improve G T _ _ ⟨s(a, b), heG⟩ ⟨d.edge, hgG⟩ hSG hStree
              (hTmin _ hα.1) hSe hmemT hα.2.1 hα.2.2
  12. If e ∉ T, swapping an edge f on the path in T between a and b for e contradicts the optimality of T.

    In the tree T, there is a simple path q between a and b. Since a and b are not reachable via Z, q must contain an edge f ∉ Z. Removing f disconnects a and b in T. Swapping f for e yields a tree S ≤ G. Completing β with α giving weight 1 to f and weight 0 to e makes S strictly cheaper than T, contradicting optimality via mstid_improve.

    lines 242–268

    uses SimpleGraph.edgeSet_fromEdgeSet, SimpleGraph.not_isDiag_of_mem_edgeSet, SimpleGraph.Walk.edges_subset_edgeSet, SimpleGraph.edgeSet_mono, mstid_path_edge_not_reachable, mstid_swap_isTree, mstid_swap_edges, mstid_alpha_lemmas, mstid_subset_G, mstid_improve

          · obtain ⟨q, hq⟩ := hTtree.connected.exists_isPath a b
            have hex : ∃ f, f ∈ q.edges ∧ f ∉ Z := by
              by_contra hc
              push Not at hc
              apply hnZ
              refine ⟨q.transfer (SimpleGraph.fromEdgeSet Z) ?_⟩
              intro f hf
              rw [SimpleGraph.edgeSet_fromEdgeSet]
              exact ⟨hc f hf,
                SimpleGraph.not_isDiag_of_mem_edgeSet (G := T)
                  (SimpleGraph.Walk.edges_subset_edgeSet q hf)⟩
            obtain ⟨f, hfq, hfZ⟩ := hex
            have hfT : f ∈ T.edgeSet := SimpleGraph.Walk.edges_subset_edgeSet q hfq
            have hfG : f ∈ G.edgeSet := SimpleGraph.edgeSet_mono hTG hfT
            have hfe : f ≠ s(a, b) := fun hc => hmemT (hc ▸ hfT)
            have hnr : ¬ (T.deleteEdges {f}).Reachable a b :=
              mstid_path_edge_not_reachable T hTtree q hq hfq
            have hStree : (T.deleteEdges {f} ⊔ SimpleGraph.edge a b).IsTree :=
              mstid_swap_isTree (T := T) (e := f) (a := a) (b := b) hTtree hfT hab hmemT hnr
            have hSe : (T.deleteEdges {f} ⊔ SimpleGraph.edge a b).edgeSet =
                insert s(a, b) (T.edgeSet \ {f}) :=
              mstid_swap_edges (T := T) (e := f) (a := a) (b := b) hab
            have hα := mstid_alpha_lemmas G β Z hZmem f s(a, b) hfZ hfe hDz
            have hSG : (T.deleteEdges {f} ⊔ SimpleGraph.edge a b) ≤ G :=
              mstid_subset_G G T hTG heG hSe
            exact mstid_improve G T _ _ ⟨f, hfG⟩ ⟨s(a, b), heG⟩ hSG hStree
              (hTmin _ hα.1) hSe hfT hα.2.1 hα.2.2
  13. Conclude that every unqueried edge e is either a loop or a bridge in the minor G_β.

    Using induction on the unordered pair x = s(a, b) via Sym2.inductionOn, lift the result to all edges of G, showing that any unqueried edge e with β(e) = none is either a loop or a bridge in the minor.

    lines 269–275

    uses Sym2.inductionOn

      have key2 : ∀ (x : Sym2 V) (hx : x ∈ G.edgeSet), β ⟨x, hx⟩ = none →
          minor_edge_is_loop G β ⟨x, hx⟩ ∨ minor_edge_is_bridge G β ⟨x, hx⟩ := by
        intro x
        induction x using Sym2.inductionOn with
        | _ a b => exact key a b
      intro e he
      exact key2 (e : Sym2 V) e.2 he
Finset.sum_congr
If two finite sums have the same index set and their summands agree on every element, then the sums are equal.
Finset.card_filter
The cardinality of the subset of elements satisfying a predicate equals the sum over the set of the indicator function of that predicate.
mstid_cost_eq_card
The cost of a subgraph S under weighting α equals the number of edges of G in S that have weight 1 (α e = true).
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
Bool.noConfusion
The boolean values true and false are distinct, so true = false implies False.
Finset.card_erase_of_mem
Removing an element from a finite set that contains it decreases the set's cardinality by 1.
Set.mem_sdiff
An element belongs to A \ B if and only if it belongs to A and does not belong to B.
Set.mem_singleton_iff
An element belongs to the singleton {a} if and only if it equals a.
And.left
From a conjunction A ∧ B, one can deduce A.
SimpleGraph.edgeSet_sup
The edge set of the union (supremum) of two graphs is the union of their edge sets.
SimpleGraph.edgeSet_deleteEdges
The edge set of a graph with edges s deleted is the original edge set minus s.
SimpleGraph.edgeSet_edge
The edge set of the single-edge graph on vertices v and w is {s(v, w)} \ diagSet.
Set.union_comm
Set union is commutative: A ∪ B = B ∪ A.
Set.singleton_union
The union of a singleton {a} and a set s equals the insertion of a into s.
SimpleGraph.deleteEdges_le
Deleting edges from a graph produces a subgraph of the original graph.
mstid_swap_edges
For distinct vertices a ≠ b, the edge set of (T \ {e}) ⊔ edge(a, b) equals insert s(a, b) (T.edgeSet \ {e}).
is_tree_iff_is_acyclic_and_card
A simple graph on a finite vertex set V is a tree if and only if it is acyclic and has |V| - 1 edges.
Set.ncard_insert_of_notMem
Inserting an element into a finite set that does not contain it increases its cardinality by 1.
Set.ncard_sdiff_singleton_add_one
Removing an element from a finite set containing it yields a set whose cardinality plus 1 equals the original cardinality.
Nat.card_coe_set_eq
The cardinality Nat.card of a coerced set type equals its set counting cardinality ncard.
Sym2.ind
To prove a property for all unordered pairs, it suffices to prove it for pairs of the form s(x, y).
SimpleGraph.reachable_deleteEdges_iff_exists_walk
Two vertices are reachable in G \ {s(v, w)} if and only if there is a walk between them in G avoiding s(v, w).
SimpleGraph.Walk.edges_toPath_subset_edges
The edges of the simple path obtained from a walk form a subset of the walk's edges.
mstid_cost_swap
Replacing an edge of weight 1 with an edge of weight 0 in a tree decreases its cost under α by 1.
Finset.card_pos
A finite set has strictly positive cardinality if and only if it is non-empty.
if_pos
If condition c holds, then (if c then t else e) equals t.
Option.some.inj
If some a = some b in Option, then a = b.
if_neg
If condition c does not hold, then (if c then t else e) equals e.
Or.inl
From proposition A, one can deduce A ∨ B.
Or.inr
From proposition B, one can deduce A ∨ B.
SimpleGraph.edgeSet_mono
If G₁ ≤ G₂, then the edge set of G₁ is a subset of the edge set of G₂.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) belongs to the edge set of G if and only if v and w are adjacent in G.
SimpleGraph.isAcyclic_iff_forall_adj_isBridge
A graph is acyclic if and only if every edge in the graph is a bridge.
SimpleGraph.Reachable.rfl
Every vertex is reachable from itself in any graph.
List.mem_map_of_mem
If an element a is in a list l, then f(a) is in the mapped list List.map f l.
SimpleGraph.Walk.edges_subset_edgeSet
Every edge used in a walk in G belongs to the edge set of G.
SimpleGraph.deleteEdges_adj
Vertices v and w are adjacent in G \ s if and only if they are adjacent in G and s(v, w) ∉ s.
mstid_swap_isTree
If T is a tree, e ∈ T, a ≠ b, s(a, b) ∉ T, and a, b are not reachable in T \ {e}, then (T \ {e}) ⊔ edge(a, b) is a tree.
mstid_alpha_lemmas
The edge weighting assigning weight 0 to Z ∪ {addG} and weight 1 elsewhere is consistent with β, assigns weight 1 to remG, and assigns weight 0 to addG.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
mstid_subset_G
If T ≤ G and add ∈ G.edgeSet, then (T \ {rem}) ∪ {add} is also a subgraph of G.
mstid_improve
Swapping a weight-1 edge for a weight-0 edge in a minimum spanning tree produces a strictly cheaper spanning tree, deriving a contradiction.
SimpleGraph.edgeSet_fromEdgeSet
The edge set of the graph generated by a set of pairs s is s minus the diagonal.
SimpleGraph.not_isDiag_of_mem_edgeSet
Any edge of a simple graph connects two distinct vertices, so it is not on the diagonal.
mstid_path_edge_not_reachable
In a tree, deleting any edge that lies on the unique path between two vertices disconnects them.
Sym2.inductionOn
To prove a property for an unordered pair, it suffices to prove it for pairs of the form s(a, b).

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

open scoped Classicalprivate noncomputable def mstid_cost {V : Type*} [Fintype V]    (G : SimpleGraph V) (α : G.edgeSet → Bool) (S : SimpleGraph V) : ℕ :=  ∑ e : G.edgeSet, if (e : Sym2 V) ∈ S.edgeSet then (if α e then 1 else 0) else 0private lemma mstid_cost_eq_card {V : Type*} [Fintype V]    (G : SimpleGraph V) (α : G.edgeSet → Bool) (S : SimpleGraph V) :    mstid_cost G α S = ((Finset.univ : Finset G.edgeSet).filter      (fun e : G.edgeSet => (e : Sym2 V) ∈ S.edgeSet ∧ α e = true)).card := by  classical  have h1 : mstid_cost G α S = ∑ e : G.edgeSet,      (if ((e : Sym2 V) ∈ S.edgeSet ∧ α e = true) then (1:ℕ) else 0) := by    refine Finset.sum_congr rfl ?_    intro e _    by_cases h : (e : Sym2 V) ∈ S.edgeSet <;> by_cases hb : α e <;> simp [h, hb]  rw [h1, ← Finset.card_filter]private lemma mstid_cost_swap {V : Type*} [Fintype V] (G T S : SimpleGraph V)    (α : G.edgeSet → Bool) (remG addG : G.edgeSet)    (hS : S.edgeSet = insert (addG : Sym2 V) (T.edgeSet \ {(remG : Sym2 V)}))    (hrem : (remG : Sym2 V) ∈ T.edgeSet)    (hαrem : α remG = true) (hαadd : α addG = false) :    mstid_cost G α S = mstid_cost G α T - 1 := by  classical  rw [mstid_cost_eq_card, mstid_cost_eq_card]  have hfil : ((Finset.univ : Finset G.edgeSet).filter        (fun e : G.edgeSet => (e : Sym2 V) ∈ S.edgeSet ∧ α e = true)) =      (((Finset.univ : Finset G.edgeSet).filter        (fun e : G.edgeSet => (e : Sym2 V) ∈ T.edgeSet ∧ α e = true)).erase remG) := by    ext x    simp only [Finset.mem_filter, Finset.mem_univ, Finset.mem_erase, true_and]    constructor    · rintro ⟨hmem, hαx⟩      rw [hS] at hmem      rcases hmem with hx | ⟨hxt, hxne⟩      · exfalso        have hx' : x = addG := Subtype.ext hx        rw [hx'] at hαx        rw [hαx] at hαadd        exact Bool.noConfusion hαadd      · exact ⟨fun h => hxne (congrArg Subtype.val h), hxt, hαx⟩    · rintro ⟨hxne, hxt, hαx⟩      refine ⟨?_, hαx⟩      rw [hS]      exact Or.inr ⟨hxt, fun h => hxne (Subtype.ext h)⟩  rw [hfil, Finset.card_erase_of_mem]  simp [hrem, hαrem]private lemma mstid_swap_edges {V : Type*} (T : SimpleGraph V) {e : Sym2 V} {a b : V}    (hab : a ≠ b) :    (T.deleteEdges {e} ⊔ SimpleGraph.edge a b).edgeSet =      insert s(a, b) (T.edgeSet \ {e}) := by  classical  have hdiag : s(a, b) ∉ Sym2.diagSet := by simpa using hab  have hsing : ({s(a, b)} : Set (Sym2 V)) \ Sym2.diagSet = {s(a, b)} := by    ext x    simp only [Set.mem_sdiff, Set.mem_singleton_iff]    exact ⟨And.left, fun hx => ⟨hx, fun hx' => hdiag (hx ▸ hx')⟩⟩  rw [SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_deleteEdges, SimpleGraph.edgeSet_edge,    hsing, Set.union_comm, Set.singleton_union]private lemma mstid_swap_isTree    {V : Type*} [Fintype V] (T : SimpleGraph V) (hT : T.IsTree)    {e : Sym2 V} (he : e ∈ T.edgeSet) {a b : V} (hab : a ≠ b) (hne : s(a, b) ∉ T.edgeSet)    (hnr : ¬ (T.deleteEdges {e}).Reachable a b) :    (T.deleteEdges {e} ⊔ SimpleGraph.edge a b).IsTree := by  classical  have hacyc : (T.deleteEdges {e}).IsAcyclic := hT.isAcyclic.anti (SimpleGraph.deleteEdges_le _)  have hSacyc : (T.deleteEdges {e} ⊔ SimpleGraph.edge a b).IsAcyclic :=    hacyc.sup_edge_of_not_reachable hnr  have h_edges := mstid_swap_edges (T := T) (e := e) (a := a) (b := b) hab  rw [is_tree_iff_is_acyclic_and_card]  refine ⟨hSacyc, ?_⟩  have hcardT : Nat.card T.edgeSet + 1 = Nat.card V :=    (is_tree_iff_is_acyclic_and_card T).mp hT |>.2  have key : ((T.deleteEdges {e} ⊔ SimpleGraph.edge a b).edgeSet).ncard = T.edgeSet.ncard := by    rw [h_edges, Set.ncard_insert_of_notMem (fun h => hne h.1)]    exact Set.ncard_sdiff_singleton_add_one he  rw [Nat.card_coe_set_eq, key, ← Nat.card_coe_set_eq]  exact hcardTprivate lemma mstid_path_edge_not_reachable {V : Type*} (T : SimpleGraph V) (hT : T.IsTree)    {u v : V} (q : T.Walk u v) (hq : q.IsPath) {f : Sym2 V} (hf : f ∈ q.edges) :    ¬ (T.deleteEdges {f}).Reachable u v := by  classical  have key : ∀ f : Sym2 V,      ((T.deleteEdges {f}).Reachable u v ↔ ∃ p : T.Walk u v, f ∉ p.edges) :=    fun f => @Sym2.ind V      (fun g => ((T.deleteEdges {g}).Reachable u v ↔ ∃ p : T.Walk u v, g ∉ p.edges))      (fun a b => SimpleGraph.reachable_deleteEdges_iff_exists_walk) f  intro h  rw [key f] at h  obtain ⟨p, hp⟩ := h  have huniq : (↑p.toPath : T.Walk u v) = q := (hT.existsUnique_path u v).unique p.toPath.isPath hq  exact hp (SimpleGraph.Walk.edges_toPath_subset_edges p (huniq ▸ hf))private lemma mstid_improve {V : Type*} [Fintype V] (G T S : SimpleGraph V)    (α : G.edgeSet → Bool) (remG addG : G.edgeSet)    (hSG : S ≤ G) (hS : S.IsTree) (hmin : is_mst_for G T α)    (hSed : S.edgeSet = insert (addG : Sym2 V) (T.edgeSet \ {(remG : Sym2 V)}))    (hrem : (remG : Sym2 V) ∈ T.edgeSet)    (hαrem : α remG = true) (hαadd : α addG = false) : False := by  have h1 : mstid_cost G α T ≤ mstid_cost G α S := hmin.2.2 S hSG hS  have h2 : mstid_cost G α S = mstid_cost G α T - 1 :=    mstid_cost_swap G T S α remG addG hSed hrem hαrem hαadd  have hpos : 1 ≤ mstid_cost G α T := by    rw [mstid_cost_eq_card]    have hmem : remG ∈ ((Finset.univ : Finset G.edgeSet).filter        (fun e : G.edgeSet => (e : Sym2 V) ∈ T.edgeSet ∧ α e = true)) := by      simp [hrem, hαrem]    exact Finset.card_pos.mpr ⟨remG, hmem⟩  omegaprivate lemma mstid_alpha_lemmas {V : Type*} (G : SimpleGraph V)    (β : G.edgeSet → Option Bool) (Z : Set (Sym2 V))    (hZmem : ∀ x : G.edgeSet, ((x : Sym2 V) ∈ Z ↔ β x = some false))    (remG addG : Sym2 V) (hneZ : remG ∉ Z) (hneadd : remG ≠ addG)    (hDadd : ∀ x : G.edgeSet, β x = some true → (x : Sym2 V) ≠ addG) :    (∀ (x : G.edgeSet) (b : Bool), β x = some b →      (if (x : Sym2 V) ∈ Z ∨ (x : Sym2 V) = addG then false else true) = b) ∧    ((if remG ∈ Z ∨ remG = addG then false else true) = true) ∧    ((if addG ∈ Z ∨ addG = addG then false else true) = false) := by  refine ⟨?_, ?_, ?_⟩  · intro x b hb    by_cases h : (x : Sym2 V) ∈ Z ∨ (x : Sym2 V) = addG    · rw [if_pos h]      rcases h with h1 | h2      · rw [(hZmem x).mp h1] at hb        rw [Option.some.inj hb]      · rcases b with _ | _        · rfl        · exact absurd hb (hDadd x · h2)    · rw [if_neg h]      rcases b with _ | _      · exact absurd ((hZmem x).mpr hb) (fun hc => h (Or.inl hc))      · rfl  · rw [if_neg]    exact fun hc => hc.elim hneZ hneadd  · rw [if_pos (Or.inr rfl)]private lemma mstid_subset_G {V : Type*} (G T : SimpleGraph V) (hTG : T ≤ G)    {rem add : Sym2 V} (haddG : add ∈ G.edgeSet)    {S : SimpleGraph V} (hS : S.edgeSet = insert add (T.edgeSet \ {rem})) : S ≤ G := by  intro x y hxy  have hx : s(x, y) ∈ S.edgeSet := hxy  rw [hS] at hx  rcases hx with rfl | ⟨hx, _⟩  · exact haddG  · exact SimpleGraph.edgeSet_mono hTG hxopen scoped Classical in/-- If β certifies an MST, then every unqueried edge in the minor is a loop or bridge. -/theorem mst_id_certificate_imp_minor_edges_loop_or_bridge {V : Type*} [Fintype V]    (G : SimpleGraph V) (hG : G.Connected) (β : G.edgeSet → Option Bool)    (hcert : is_mst_certificate G β) :    ∀ (e : G.edgeSet), β e = none →      minor_edge_is_loop G β e ∨ minor_edge_is_bridge G β e := by  classical  obtain ⟨T, hTG, hTtree, hTmin⟩ := hcert  set Z : Set (Sym2 V) := {s | ∃ (h : s ∈ G.edgeSet), β ⟨s, h⟩ = some false} with hZdef  set D : Set (Sym2 V) := {s | ∃ (h : s ∈ G.edgeSet), β ⟨s, h⟩ = some true} with hDdef  have hZmem : ∀ x : G.edgeSet, ((x : Sym2 V) ∈ Z ↔ β x = some false) := by    intro x    refine ⟨?_, ?_⟩    · rintro ⟨h, hb⟩      rwa [show (⟨(x : Sym2 V), h⟩ : G.edgeSet) = x from Subtype.ext rfl] at hb    · intro hb      exact ⟨x.2, by rwa [show (⟨(x : Sym2 V), x.2⟩ : G.edgeSet) = x from Subtype.ext rfl]⟩  have hDmem : ∀ x : G.edgeSet, ((x : Sym2 V) ∈ D ↔ β x = some true) := by    intro x    refine ⟨?_, ?_⟩    · rintro ⟨h, hb⟩      rwa [show (⟨(x : Sym2 V), h⟩ : G.edgeSet) = x from Subtype.ext rfl] at hb    · intro hb      exact ⟨x.2, by rwa [show (⟨(x : Sym2 V), x.2⟩ : G.edgeSet) = x from Subtype.ext rfl]⟩  have key : ∀ (a b : V) (heG : s(a, b) ∈ G.edgeSet),      β ⟨s(a, b), heG⟩ = none →      minor_edge_is_loop G β ⟨s(a, b), heG⟩ ∨ minor_edge_is_bridge G β ⟨s(a, b), heG⟩ := by    intro a b heG hnone    by_cases hloop : minor_edge_is_loop G β ⟨s(a, b), heG⟩    · exact Or.inl hloop    · right      have hab : a ≠ b := (SimpleGraph.mem_edgeSet G).mp heG |>.ne      have hnZ : ¬ (SimpleGraph.fromEdgeSet Z).Reachable a b :=        fun h => hloop ⟨a, b, rfl, h⟩      have hzt : s(a, b) ∉ Z := by        intro hc        rw [(hZmem ⟨s(a, b), heG⟩).mp hc] at hnone        exact absurd hnone (by simp)      have hDz : ∀ x : G.edgeSet, β x = some true → (x : Sym2 V) ≠ s(a, b) := by        intro x hx hc        have hxD : (x : Sym2 V) ∈ D := (hDmem x).mpr hx        rw [hc] at hxD        rw [(hDmem ⟨s(a, b), heG⟩).mp hxD] at hnone        exact absurd hnone (by simp)      refine ⟨a, b, rfl, hnZ, ?_⟩      intro hreach      by_cases hmemT : s(a, b) ∈ T.edgeSet      · have hbridge : T.IsBridge s(a, b) :=          SimpleGraph.isAcyclic_iff_forall_adj_isBridge.mp hTtree.isAcyclic            ((SimpleGraph.mem_edgeSet T).mp hmemT)        set S₀ : Set V := {v | (T.deleteEdges {s(a, b)}).Reachable a v} with hS₀        have haS : a ∈ S₀ := SimpleGraph.Reachable.rfl        have hbS : b ∉ S₀ := hbridge        obtain ⟨p⟩ := hreach        obtain ⟨d, hdmem, hdfst, hdsnd⟩ := p.exists_boundary_dart S₀ haS hbS        have hgp : d.edge ∈ p.edges := by          have h := List.mem_map_of_mem (f := SimpleGraph.Dart.edge) hdmem          simpa [SimpleGraph.Walk.edges] using h        have hgdel := SimpleGraph.Walk.edges_subset_edgeSet p hgp        rw [SimpleGraph.edgeSet_deleteEdges] at hgdel        have hgG : d.edge ∈ G.edgeSet := hgdel.1        have hgnD : d.edge ∉ D := fun hc => hgdel.2 (Or.inr hc)        have hgne : d.edge ≠ s(a, b) := fun hc => hgdel.2 (Or.inl hc)        have huv_ne : d.toProd.1 ≠ d.toProd.2 := by          intro hc          exact hdsnd (hc ▸ hdfst)        have hneT : d.edge ∉ T.edgeSet := by          intro hT'          have hTadj : T.Adj d.toProd.1 d.toProd.2 := (SimpleGraph.mem_edgeSet T).mp hT'          have hadj : (T.deleteEdges {s(a, b)}).Adj d.toProd.1 d.toProd.2 := by            rw [SimpleGraph.deleteEdges_adj]            exact ⟨hTadj, hgne⟩          exact hdsnd (hdfst.trans hadj.reachable)        have hnr : ¬ (T.deleteEdges {s(a, b)}).Reachable d.toProd.1 d.toProd.2 :=          fun hc => hdsnd (hdfst.trans hc)        have hStree : (T.deleteEdges {s(a, b)} ⊔ SimpleGraph.edge d.toProd.1 d.toProd.2).IsTree :=          mstid_swap_isTree (T := T) (e := s(a, b)) (a := d.toProd.1) (b := d.toProd.2)            hTtree hmemT huv_ne hneT hnr        have hSe : (T.deleteEdges {s(a, b)} ⊔ SimpleGraph.edge d.toProd.1 d.toProd.2).edgeSet =            insert d.edge (T.edgeSet \ {s(a, b)}) :=          mstid_swap_edges (T := T) (e := s(a, b)) (a := d.toProd.1) (b := d.toProd.2) huv_ne        have hDg : ∀ x : G.edgeSet, β x = some true → (x : Sym2 V) ≠ d.edge := by          intro x hx hc          exact hgnD (hc ▸ ((hDmem x).mpr hx))        have hα := mstid_alpha_lemmas G β Z hZmem s(a, b) d.edge hzt (Ne.symm hgne) hDg        have hSG : (T.deleteEdges {s(a, b)} ⊔ SimpleGraph.edge d.toProd.1 d.toProd.2) ≤ G :=          mstid_subset_G G T hTG hgG hSe        exact mstid_improve G T _ _ ⟨s(a, b), heG⟩ ⟨d.edge, hgG⟩ hSG hStree          (hTmin _ hα.1) hSe hmemT hα.2.1 hα.2.2      · obtain ⟨q, hq⟩ := hTtree.connected.exists_isPath a b        have hex : ∃ f, f ∈ q.edges ∧ f ∉ Z := by          by_contra hc          push Not at hc          apply hnZ          refine ⟨q.transfer (SimpleGraph.fromEdgeSet Z) ?_⟩          intro f hf          rw [SimpleGraph.edgeSet_fromEdgeSet]          exact ⟨hc f hf,            SimpleGraph.not_isDiag_of_mem_edgeSet (G := T)              (SimpleGraph.Walk.edges_subset_edgeSet q hf)⟩        obtain ⟨f, hfq, hfZ⟩ := hex        have hfT : f ∈ T.edgeSet := SimpleGraph.Walk.edges_subset_edgeSet q hfq        have hfG : f ∈ G.edgeSet := SimpleGraph.edgeSet_mono hTG hfT        have hfe : f ≠ s(a, b) := fun hc => hmemT (hc ▸ hfT)        have hnr : ¬ (T.deleteEdges {f}).Reachable a b :=          mstid_path_edge_not_reachable T hTtree q hq hfq        have hStree : (T.deleteEdges {f} ⊔ SimpleGraph.edge a b).IsTree :=          mstid_swap_isTree (T := T) (e := f) (a := a) (b := b) hTtree hfT hab hmemT hnr        have hSe : (T.deleteEdges {f} ⊔ SimpleGraph.edge a b).edgeSet =            insert s(a, b) (T.edgeSet \ {f}) :=          mstid_swap_edges (T := T) (e := f) (a := a) (b := b) hab        have hα := mstid_alpha_lemmas G β Z hZmem f s(a, b) hfZ hfe hDz        have hSG : (T.deleteEdges {f} ⊔ SimpleGraph.edge a b) ≤ G :=          mstid_subset_G G T hTG heG hSe        exact mstid_improve G T _ _ ⟨f, hfG⟩ ⟨s(a, b), heG⟩ hSG hStree          (hTmin _ hα.1) hSe hfT hα.2.1 hα.2.2  have key2 : ∀ (x : Sym2 V) (hx : x ∈ G.edgeSet), β ⟨x, hx⟩ = none →      minor_edge_is_loop G β ⟨x, hx⟩ ∨ minor_edge_is_bridge G β ⟨x, hx⟩ := by    intro x    induction x using Sym2.inductionOn with    | _ a b => exact key a b  intro e he  exact key2 (e : Sym2 V) e.2 he
See it in the graphDiscuss this resultChallenge it