mst_id_certificate_imp_minor_edges_loop_or_bridge
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.
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.
uses
Finset.sum_congr,Finset.card_filterclassical 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]
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.
uses
mstid_cost_eq_card,Subtype.ext,Bool.noConfusion,Finset.card_erase_of_memprivate 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]
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.
uses
Set.mem_sdiff,Set.mem_singleton_iff,And.left,SimpleGraph.edgeSet_sup,SimpleGraph.edgeSet_deleteEdges,SimpleGraph.edgeSet_edge,Set.union_comm,Set.singleton_unionprivate 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]
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.
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_eqprivate 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
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.
uses
Sym2.ind,SimpleGraph.reachable_deleteEdges_iff_exists_walk,SimpleGraph.Walk.edges_toPath_subset_edgesprivate 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))
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.
uses
mstid_cost_swap,mstid_cost_eq_card,Finset.card_posprivate 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
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.
uses
if_pos,Option.some.inj,if_neg,Or.inl,Or.inrprivate 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)]
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.
uses
SimpleGraph.edgeSet_monoprivate 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
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.
uses
Subtype.extopen 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]⟩
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}).
uses
Or.inl,SimpleGraph.mem_edgeSethave 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
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.
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_improveby_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
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.
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
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.
uses
Sym2.inductionOnhave 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).
- The Lean formalization defines minor-edge concepts via graph reachability: contracting weight-0 edges corresponds to reachability in the subgraph of edges with β(e) = some false, while deleting weight-1 edges corresponds to edge deletion of edges with β(e) = some true.
- The overall proof is structured with eight private helper lemmas establishing the cost formula, edge-swap combinatorics, tree preservation under edge swaps, weight assignment construction, and the derivation of a contradiction from an improving swap.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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