AFTD Auto-Formalizing Theoretical Domains

residual_matching_num_single_edge_exchange_iff_critical

theoremverifiedformalization

Let G be a finite simple graph on a finite vertex type V, M a maximum matching of G, u an M-free vertex, and vw an edge of M such that uv is an edge of G. Then there exists a maximum matching M' of G with edge set (M \ {vw}) ∪ {uv}, and the matching number of the residual graph G \ M' equals ν(G \ M) + 1 if and only if the matching number of (G \ M) + vw equals ν(G \ M) + 1.

Statement

theorem residual_matching_num_single_edge_exchange_iff_critical {V : Type*} [Fintype V]
    (G : SimpleGraph V) (M : G.Subgraph) (hM : graph_is_maximum_matching G M)
    (u v w : V) (hu : u ∉ M.verts) (hvw : M.Adj v w) (huv : G.Adj u v) :
    ∃ M' : G.Subgraph,
      M'.edgeSet = (M.edgeSet \ {s(v, w)}) ∪ {s(u, v)} ∧
      graph_is_maximum_matching G M' ∧
      (graph_matching_num (G.deleteEdges M'.edgeSet) =
          graph_matching_num (G.deleteEdges M.edgeSet) + 1 ↔
        graph_matching_num ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w) =
          graph_matching_num (G.deleteEdges M.edgeSet) + 1)
Formalizes
arXiv:2610.27833, Lemma 1
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • graph_matching_numThe matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.
  • graph_matching_num_le_encard_edgeSetIn any simple graph G, the matching number is at most the cardinality of the edge set.
  • graph_matching_num_monoIf G and G' are simple graphs on the same vertex set with G ≤ G', then the matching number of G is at most the matching number of G'.
  • graph_is_maximum_matchingA subgraph M of a simple graph G is a maximum matching if M is a matching and its edge cardinality equals the matching number of G.
  • supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…

Read back from the Lean

Let $V$ be a finite type. Let $G$ be a simple graph on $V$, and let $M$ be a subgraph of $G$ which is a maximum matching of $G$ (graph_is_maximum_matching G M). Let $u, v, w \in V$ such that: 1. $u \notin M.\text{verts}$ (vertex $u$ is not in the vertex set of $M$), 2. $M.\text{Adj } v\ w$ ($v$ and $w$ are adjacent in $M$), and 3. $G.\text{Adj } u\ v$ ($u$ and $v$ are adjacent in $G$). Then there exists a subgraph $M'$ of $G$ such that: 1. The edge set of $M'$ is $(M.\text{edgeSet} \setminus \{s(v, w)\}) \cup \{s(u, v)\}$ (the edge set of $M$ with the edge between $v$ and $w$ removed and the edge between $u$ and $v$ added); 2. $M'$ is a maximum matching of $G$ (graph_is_maximum_matching G M'); and 3. The matching number of $G$ with the edges of $M'$ deleted (G.deleteEdges M'.edgeSet) equals the matching number of $G$ with the edges of $M$ deleted plus 1, if and only if the matching number of $(G.\text{deleteEdges } M.\text{edgeSet}) \sqcup \text{SimpleGraph.edge } v\ w$ (i.e. $G \setminus M$ with the edge between $v$ and $w$ added back) equals the matching number of $G$ with the edges of $M$ deleted plus 1.

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

The theorem establishes that exchanging an edge vw of a maximum matching M for an edge uv incident to an M-free vertex u produces another maximum matching M', and that the matching number of the residual graph increases by 1 if and only if adding vw to G \\ M increases its matching number by 1. The residual graph G \\ M' is an edge subgraph of (G \\ M) + vw because deleting the replacement uv is the only additional restriction, which immediately gives the forward direction by monotonicity. For the converse, any matching in (G \\ M) + vw of size strictly greater than ν(G \\ M) must contain vw, which precludes it from containing uv since v cannot be doubly matched; hence the entire matching is already contained in G \\ M', forcing its residual matching number to also increase by 1.

  1. A matching subgraph N of H whose edge set is contained in K can be copied into K as a matching with the same edge set.

    Define a subgraph N' of K with the same vertices and adjacency as N. Since its edges are a subset of K's edges, the adjacency condition holds in K, and the matching property carries over directly because it only depends on the local degree structure. The edge sets are identical by definition.

    lines 7–21

    uses SimpleGraph.Subgraph.mem_edgeSet, SimpleGraph.mem_edgeSet, Sym2.ind

      let N' : K.Subgraph :=
        { verts := N.verts
          Adj := N.Adj
          adj_sub := by
            intro x y hxy
            have hmem : s(x, y) ∈ K.edgeSet := h (by rwa [SimpleGraph.Subgraph.mem_edgeSet])
            rwa [SimpleGraph.mem_edgeSet] at hmem
          edge_vert := by
            intro x y hxy
            exact N.edge_vert hxy
          symm := N.symm }
      refine ⟨N', hN, ?_⟩
      ext e
      induction e using Sym2.ind with
      | _ x y => rw [SimpleGraph.Subgraph.mem_edgeSet, SimpleGraph.Subgraph.mem_edgeSet]
  2. Deleting an edge set T from a matching subgraph N and restricting to the support of the remaining edges produces a matching subgraph with edge set E(N) \\ T.

    Restricting the edge-deleted subgraph to its support ensures every vertex has degree at least 1, and since deleting edges cannot increase degrees, uniqueness of the matched partner is inherited from N. Expanding the definitions shows that an edge belongs to the restricted subgraph if and only if it belongs to E(N) and not T.

    lines 27–50

    uses SimpleGraph.Subgraph.induce_verts, SimpleGraph.Subgraph.mem_support, SimpleGraph.Subgraph.deleteEdges_adj, SimpleGraph.Subgraph.induce_adj, SimpleGraph.Subgraph.adj_symm, Sym2.ind, SimpleGraph.Subgraph.mem_edgeSet, Set.mem_sdiff, Sym2.eq_swap

      refine ⟨(N.deleteEdges T).induce (N.deleteEdges T).support, ?_, ?_⟩
      · intro x hx
        rw [SimpleGraph.Subgraph.induce_verts, SimpleGraph.Subgraph.mem_support] at hx
        obtain ⟨y, hxy⟩ := hx
        rw [SimpleGraph.Subgraph.deleteEdges_adj] at hxy
        refine ⟨y, ?_, ?_⟩
        · change ((N.deleteEdges T).induce (N.deleteEdges T).support).Adj x y
          rw [SimpleGraph.Subgraph.induce_adj, SimpleGraph.Subgraph.deleteEdges_adj]
          refine ⟨by rw [SimpleGraph.Subgraph.mem_support]; exact ⟨y, hxy⟩, ?_, hxy⟩
          rw [SimpleGraph.Subgraph.mem_support]; exact ⟨x, SimpleGraph.Subgraph.adj_symm _ hxy⟩
        · intro z hz
          rw [SimpleGraph.Subgraph.induce_adj, SimpleGraph.Subgraph.deleteEdges_adj] at hz
          exact (hN hxy.1.fst_mem).unique hz.2.2.1 hxy.1
      · ext e
        refine Sym2.ind (fun x y => ?_) e
        rw [SimpleGraph.Subgraph.mem_edgeSet, SimpleGraph.Subgraph.induce_adj,
            SimpleGraph.Subgraph.deleteEdges_adj, Set.mem_sdiff, SimpleGraph.Subgraph.mem_edgeSet]
        simp only [SimpleGraph.Subgraph.mem_support]
        constructor
        · rintro ⟨_, _, h, hT⟩; exact ⟨h, hT⟩
        · rintro ⟨h, hT⟩
          refine ⟨⟨y, ?_⟩, ⟨x, ?_⟩, h, hT⟩
          · rw [SimpleGraph.Subgraph.deleteEdges_adj]; exact ⟨h, hT⟩
          · rw [SimpleGraph.Subgraph.deleteEdges_adj]; exact ⟨SimpleGraph.Subgraph.adj_symm N h, by rwa [Sym2.eq_swap]⟩
  3. Deleting vw from matching M and adding uv (where u is unsaturated) gives a valid matching M' with edge set (E(M) \\ {vw}) ∪ {uv}.

    Delete vw from M using the previous lemma to obtain matching D. The support of D cannot contain u (which is not in M at all) nor v (as its only incident edge in M was vw, which was deleted). Thus D and the single edge uv have disjoint supports, so their union is a matching with the desired edge set.

    lines 56–85

    uses residual_matching_num_single_edge_exchange_iff_critical_del, SimpleGraph.support_subgraphOfAdj, Set.disjoint_insert_right, Set.disjoint_singleton_right, SimpleGraph.Subgraph.mem_support, SimpleGraph.Subgraph.mem_edgeSet, Set.mem_sdiff, Set.mem_singleton, SimpleGraph.Subgraph.IsMatching.sup, SimpleGraph.Subgraph.IsMatching.subgraphOfAdj, SimpleGraph.Subgraph.edgeSet_sup, SimpleGraph.edgeSet_subgraphOfAdj

      obtain ⟨D, hDmatch, hDedge⟩ := residual_matching_num_single_edge_exchange_iff_critical_del hM {s(v, w)}
      have hdisj : Disjoint D.support (G.subgraphOfAdj huv).support := by
        rw [SimpleGraph.support_subgraphOfAdj]
        rw [Set.disjoint_insert_right, Set.disjoint_singleton_right]
        constructor
        · intro huD
          have : D.support ⊆ M.verts := by
            intro x hx
            rw [SimpleGraph.Subgraph.mem_support] at hx
            obtain ⟨y, hy⟩ := hx
            have : s(x, y) ∈ D.edgeSet := by rwa [SimpleGraph.Subgraph.mem_edgeSet]
            rw [hDedge] at this
            have hMadj : M.Adj x y := by
              have := this.1
              rwa [SimpleGraph.Subgraph.mem_edgeSet] at this
            exact hMadj.fst_mem
          exact hu (this huD)
        · intro hvD
          rw [SimpleGraph.Subgraph.mem_support] at hvD
          obtain ⟨z, hz⟩ := hvD
          have : s(v, z) ∈ D.edgeSet := by rwa [SimpleGraph.Subgraph.mem_edgeSet]
          rw [hDedge, Set.mem_sdiff, SimpleGraph.Subgraph.mem_edgeSet] at this
          have hMadj : M.Adj v z := this.1
          have hnot : s(v, z) ∉ ({s(v, w)} : Set (Sym2 V)) := this.2
          have hz_eq_w : z = w := (hM hvw.fst_mem).unique hMadj hvw
          subst hz_eq_w
          exact hnot (Set.mem_singleton _)
      refine ⟨D ⊔ G.subgraphOfAdj huv, ?_, ?_⟩
      · exact SimpleGraph.Subgraph.IsMatching.sup hDmatch (SimpleGraph.Subgraph.IsMatching.subgraphOfAdj huv) hdisj
      · rw [SimpleGraph.Subgraph.edgeSet_sup, hDedge, SimpleGraph.edgeSet_subgraphOfAdj]
  4. For any set E with a ∈ E and b ∉ E, the set (E \\ {a}) ∪ {b} has the same extended cardinality as E.

    Since b ∉ E \\ {a}, the union is disjoint, so its cardinality is |E \\ {a}| + 1. Since a ∈ E, |E \\ {a}| + 1 = |E|.

    lines 90–94

    uses Set.disjoint_singleton_right, Set.encard_union_eq, Set.encard_singleton, Set.encard_sdiff_add_encard_of_subset

      have hd : Disjoint (E \ {a}) ({b} : Set α) := by
        rw [Set.disjoint_singleton_right]
        rintro ⟨h, -⟩
        exact hb h
      rw [Set.encard_union_eq hd, Set.encard_singleton, ← Set.encard_sdiff_add_encard_of_subset (Set.singleton_subset_iff.mpr ha), Set.encard_singleton]
  5. The matching number of any graph on a finite vertex type is finite (not ⊤).

    Because the vertex set is finite, the edge set is finite, so its extended cardinality is not ⊤. The matching number is bounded by the cardinality of the edge set, hence it is also finite.

    lines 99–102

    uses Set.encard_ne_top_iff, Set.toFinite, ne_top_of_le_ne_top, graph_matching_num_le_encard_edgeSet

      have : H.edgeSet.encard ≠ ⊤ := by
        rw [Set.encard_ne_top_iff]
        exact Set.toFinite H.edgeSet
      exact ne_top_of_le_ne_top this (graph_matching_num_le_encard_edgeSet H)
  6. The matching number is monotone with respect to edge set inclusion.

    If every edge of H is an edge of K, then H ≤ K as simple graphs, and by monotonicity of the matching number, ν(H) ≤ ν(K).

    lines 107–110

    uses graph_matching_num_mono, SimpleGraph.mem_edgeSet

      apply graph_matching_num_mono
      intro x y hxy
      have : s(x, y) ∈ K.edgeSet := h (by rwa [SimpleGraph.mem_edgeSet])
      rwa [SimpleGraph.mem_edgeSet] at this
  7. If a ≠ ⊤ in ℕ∞, b ≤ a + 1, and a < b, then b = a + 1.

    For a ≠ ⊤, the condition a < b is equivalent to a + 1 ≤ b. Combined with b ≤ a + 1, antisymmetry gives b = a + 1.

    lines 114–115

    uses ENat.add_one_le_iff, le_antisymm

      have : a + 1 ≤ b := (ENat.add_one_le_iff ha).mpr h2
      exact le_antisymm h1 this
  8. Adding a single edge to any graph increases the matching number by at most 1: ν(H ⊔ edge u v) ≤ ν(H) + 1.

    For any matching N in H ⊔ edge u v, either uv ∈ N or uv ∉ N. If uv ∈ N, deleting uv gives a matching in H of size |N| - 1, so |N| ≤ ν(H) + 1. If uv ∉ N, then N is already a matching in H, so |N| ≤ ν(H) ≤ ν(H) + 1. Taking the supremum over all such N yields ν(H ⊔ edge u v) ≤ ν(H) + 1.

    lines 120–161

    uses residual_matching_num_single_edge_exchange_iff_critical_del, SimpleGraph.edgeSet_sup, Set.mem_union, SimpleGraph.edgeSet_edge, Set.mem_singleton_iff, residual_matching_num_single_edge_exchange_iff_critical_copy, le_iSup_of_le, le_rfl, Set.encard_singleton, Set.encard_sdiff_add_encard_of_subset, False.elim, le_trans, le_self_add

      unfold graph_matching_num
      apply iSup_le
      intro N
      apply iSup_le
      intro hN
      by_cases hmem : s(u, v) ∈ N.edgeSet
      · obtain ⟨N0, hN0match, hN0edge⟩ := residual_matching_num_single_edge_exchange_iff_critical_del hN {s(u, v)}
        have hsub : N0.edgeSet ⊆ H.edgeSet := by
          rw [hN0edge]
          intro e he
          have heN : e ∈ (H ⊔ SimpleGraph.edge u v).edgeSet := N.edgeSet_subset he.1
          rw [SimpleGraph.edgeSet_sup, Set.mem_union] at heN
          rcases heN with heH | heE
          · exact heH
          · rw [SimpleGraph.edgeSet_edge] at heE
            exfalso
            exact he.2 (Set.mem_singleton_iff.mpr heE.1)
        obtain ⟨N', hN'match, hN'edge⟩ := residual_matching_num_single_edge_exchange_iff_critical_copy N0 hN0match hsub
        have hle : N'.edgeSet.encard ≤ ⨆ (M : H.Subgraph) (_ : M.IsMatching), M.edgeSet.encard :=
          le_iSup_of_le N' (le_iSup_of_le hN'match le_rfl)
        have heq : N.edgeSet.encard = N0.edgeSet.encard + 1 := by
          rw [hN0edge]
          have hsing : ({s(u, v)} : Set (Sym2 V)).encard = 1 := Set.encard_singleton _
          rw [← hsing]
          exact (Set.encard_sdiff_add_encard_of_subset (Set.singleton_subset_iff.mpr hmem)).symm
        rw [heq, ← hN'edge]
        gcongr
      · have hsub : N.edgeSet ⊆ H.edgeSet := by
          intro e he
          have heN : e ∈ (H ⊔ SimpleGraph.edge u v).edgeSet := N.edgeSet_subset he
          rw [SimpleGraph.edgeSet_sup, Set.mem_union] at heN
          rcases heN with heH | heE
          · exact heH
          · rw [SimpleGraph.edgeSet_edge] at heE
            have : e = s(u, v) := heE.1
            subst this
            exact False.elim (hmem he)
        obtain ⟨N', hN'match, hN'edge⟩ := residual_matching_num_single_edge_exchange_iff_critical_copy N hN hsub
        have hle : N'.edgeSet.encard ≤ ⨆ (M : H.Subgraph) (_ : M.IsMatching), M.edgeSet.encard :=
          le_iSup_of_le N' (le_iSup_of_le hN'match le_rfl)
        rw [← hN'edge]
        exact le_trans hle le_self_add
  9. The residual graph G \\ M' is an edge subgraph of (G \\ M) ⊔ edge v w.

    The edges of G \\ M' are those in G not in (M \\ {vw}) ∪ {uv}. If such an edge is vw, it belongs to edge v w; otherwise, since it is not in M \\ {vw} and not vw, it cannot be in M, so it belongs to G \\ M. In both cases it belongs to (G \\ M) ⊔ edge v w.

    lines 168–184

    uses SimpleGraph.edgeSet_deleteEdges, Set.mem_sdiff, SimpleGraph.edgeSet_sup, Set.mem_union, SimpleGraph.edgeSet_edge, Set.mem_singleton_iff, Sym2.mk_isDiag_iff

      intro e he
      rw [SimpleGraph.edgeSet_deleteEdges, Set.mem_sdiff] at he
      rw [SimpleGraph.edgeSet_sup, Set.mem_union, SimpleGraph.edgeSet_deleteEdges, Set.mem_sdiff]
      by_cases hevw : e = s(v, w)
      · right
        subst hevw
        rw [SimpleGraph.edgeSet_edge, Set.mem_sdiff, Set.mem_singleton_iff]
        refine ⟨rfl, ?_⟩
        intro hd
        exact hvw.ne (Sym2.mk_isDiag_iff.mp hd)
      · left
        refine ⟨he.1, ?_⟩
        intro heM
        have : e ∈ (M.edgeSet \ {s(v, w)}) ∪ {s(u, v)} := by
          left
          exact ⟨heM, hevw⟩
        exact he.2 this
  10. Any edge of (G \\ M) ⊔ edge v w distinct from uv belongs to G \\ M'.

    An edge in (G \\ M) ⊔ edge v w is either in G \\ M (hence not in M, and distinct from uv, so not in (M \\ {vw}) ∪ {uv}) or is vw (which is in G and not in M \\ {vw} nor equal to uv). In both cases it belongs to G \\ M'.

    lines 192–208

    uses SimpleGraph.edgeSet_sup, Set.mem_union, SimpleGraph.edgeSet_deleteEdges, Set.mem_sdiff, Set.mem_singleton_iff, SimpleGraph.edgeSet_edge, SimpleGraph.mem_edgeSet

      rw [SimpleGraph.edgeSet_sup, Set.mem_union, SimpleGraph.edgeSet_deleteEdges, Set.mem_sdiff] at heH
      rw [SimpleGraph.edgeSet_deleteEdges, Set.mem_sdiff, Set.mem_union, Set.mem_singleton_iff]
      rcases heH with ⟨heG, heM⟩ | heE
      · refine ⟨heG, ?_⟩
        rintro (⟨heM2, -⟩ | rfl)
        · exact heM heM2
        · exact hne rfl
      · rw [SimpleGraph.edgeSet_edge, Set.mem_sdiff, Set.mem_singleton_iff] at heE
        have he_eq : e = s(v, w) := heE.1
        subst he_eq
        have hvwG : s(v, w) ∈ G.edgeSet := by
          rw [SimpleGraph.mem_edgeSet]
          exact M.adj_sub hvw
        refine ⟨hvwG, ?_⟩
        rintro (⟨-, hnot⟩ | h_eq)
        · exact hnot rfl
        · exact hne h_eq
  11. If a matching K contains vw, it cannot contain uv.

    If K contained both vw and uv, then vertex v would be matched to both w and u in K. By the uniqueness of matched partners, this would imply u = w. But u ∉ V(M) while w ∈ V(M), a contradiction.

    lines 215–222

    uses SimpleGraph.Subgraph.mem_edgeSet, SimpleGraph.Subgraph.adj_symm

        s(u, v) ∉ K.edgeSet := by
      intro huvK
      have hKvw : K.Adj v w := by rwa [SimpleGraph.Subgraph.mem_edgeSet] at hvwK
      have hKuv : K.Adj u v := by rwa [SimpleGraph.Subgraph.mem_edgeSet] at huvK
      have hKvu : K.Adj v u := SimpleGraph.Subgraph.adj_symm K hKuv
      have hu_eq_w : u = w := (hK hKvw.fst_mem).unique hKvu hKvw
      subst hu_eq_w
      exact hu hvw.snd_mem
  12. The exchanged matching M' is a maximum matching of G.

    Because u ∉ V(M), uv cannot be in M. Replacing vw by uv gives a matching M' with the same cardinality as M by the cardinality lemma, so M' is also a maximum matching.

    lines 235–244

    uses SimpleGraph.Subgraph.mem_edgeSet, residual_matching_num_single_edge_exchange_iff_critical_replace, residual_matching_num_single_edge_exchange_iff_critical_card

      obtain ⟨hMmatch, hMcard⟩ := hM
      have hbE : s(u, v) ∉ M.edgeSet := fun h =>
        hu (M.edge_vert (by rwa [SimpleGraph.Subgraph.mem_edgeSet] at h))
      obtain ⟨M', hM'match, hM'edge⟩ :=
        residual_matching_num_single_edge_exchange_iff_critical_replace hMmatch hu hvw huv
      have hM'card : graph_is_maximum_matching G M' := by
        refine ⟨hM'match, ?_⟩
        rw [hM'edge, residual_matching_num_single_edge_exchange_iff_critical_card M.edgeSet (by rw [SimpleGraph.Subgraph.mem_edgeSet]; exact hvw) hbE,
          hMcard]
      refine ⟨M', hM'edge, hM'card, ?_⟩
  13. Both ν(G \\ M') and ν((G \\ M) ⊔ edge v w) are bounded above by μ + 1, where μ = ν(G \\ M).

    Adding the single edge vw to G \\ M increases the matching number by at most 1, so ν((G \\ M) ⊔ edge v w) ≤ μ + 1. Since G \\ M' is an edge subgraph of (G \\ M) ⊔ edge v w, monotonicity gives ν(G \\ M') ≤ ν((G \\ M) ⊔ edge v w) ≤ μ + 1.

    lines 245–254

    uses residual_matching_num_single_edge_exchange_iff_critical_num_ne_top, ENat.lt_add_one_iff, le_rfl, le_trans, residual_matching_num_single_edge_exchange_iff_critical_num_mono, residual_matching_num_single_edge_exchange_iff_critical_upper, residual_matching_num_single_edge_exchange_iff_critical_one_edge

      rw [hM'edge]
      set μ := graph_matching_num (G.deleteEdges M.edgeSet)
      have hμtop : μ ≠ ⊤ := residual_matching_num_single_edge_exchange_iff_critical_num_ne_top _
      have hone : μ < μ + 1 := (ENat.lt_add_one_iff hμtop).mpr le_rfl
      have hupper : graph_matching_num (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})) ≤ μ + 1 :=
        le_trans
          (residual_matching_num_single_edge_exchange_iff_critical_num_mono (residual_matching_num_single_edge_exchange_iff_critical_upper hvw))
          (residual_matching_num_single_edge_exchange_iff_critical_one_edge _ v w)
      have hHup : graph_matching_num ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w) ≤ μ + 1 :=
        residual_matching_num_single_edge_exchange_iff_critical_one_edge _ v w
  14. If ν(G \\ M') = μ + 1, then ν((G \\ M) ⊔ edge v w) = μ + 1.

    Since G \\ M' is a subgraph of (G \\ M) ⊔ edge v w, we have μ < μ + 1 = ν(G \\ M') ≤ ν((G \\ M) ⊔ edge v w) ≤ μ + 1. Because the value is strictly greater than μ and at most μ + 1, it must equal μ + 1.

    lines 255–262

    uses residual_matching_num_single_edge_exchange_iff_critical_lt_succ_eq, residual_matching_num_single_edge_exchange_iff_critical_num_mono, residual_matching_num_single_edge_exchange_iff_critical_upper

      constructor
      · intro h
        refine residual_matching_num_single_edge_exchange_iff_critical_lt_succ_eq hμtop hHup ?_
        calc μ < μ + 1 := hone
          _ = graph_matching_num (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})) := h.symm
          _ ≤ graph_matching_num ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w) :=
            residual_matching_num_single_edge_exchange_iff_critical_num_mono (residual_matching_num_single_edge_exchange_iff_critical_upper hvw)
      · intro h
  15. If ν((G \\ M) ⊔ edge v w) = μ + 1, any matching K witnessing size > μ must contain vw.

    Assume ν((G \\ M) ⊔ edge v w) = μ + 1. Then there exists a matching K in (G \\ M) ⊔ edge v w with |K| > μ. If vw ∉ K, then K would be contained entirely in G \\ M, which would imply |K| ≤ μ, contradicting |K| > μ. Thus vw must belong to K.

    lines 263–288

    uses lt_iSup_iff, SimpleGraph.edgeSet_sup, Set.mem_union, SimpleGraph.edgeSet_edge, False.elim, residual_matching_num_single_edge_exchange_iff_critical_copy, le_iSup_of_le, le_rfl, lt_irrefl, lt_of_le_of_lt

        have hlt : μ < graph_matching_num ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w) := by
          rw [h]
          exact hone
        unfold graph_matching_num at hlt
        rw [lt_iSup_iff] at hlt
        obtain ⟨K, hK⟩ := hlt
        rw [lt_iSup_iff] at hK
        obtain ⟨hKmatch, hKencard⟩ := hK
        have hvwK : s(v, w) ∈ K.edgeSet := by
          by_contra hnot
          have hsub : K.edgeSet ⊆ (G.deleteEdges M.edgeSet).edgeSet := by
            intro e he
            have heH : e ∈ ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w).edgeSet := K.edgeSet_subset he
            rw [SimpleGraph.edgeSet_sup, Set.mem_union] at heH
            rcases heH with he1 | he2
            · exact he1
            · rw [SimpleGraph.edgeSet_edge] at he2
              have : e = s(v, w) := he2.1
              subst this
              exact False.elim (hnot he)
          obtain ⟨K', hK'match, hK'edge⟩ := residual_matching_num_single_edge_exchange_iff_critical_copy K hKmatch hsub
          have hle : K'.edgeSet.encard ≤ μ :=
            le_iSup_of_le K' (le_iSup_of_le hK'match le_rfl)
          rw [hK'edge] at hle
          exact lt_irrefl _ (lt_of_le_of_lt hle hKencard)
        have huvK : s(u, v) ∉ K.edgeSet :=
  16. The witness matching K is contained in G \\ M', so ν(G \\ M') = μ + 1.

    Since vw ∈ K, the matching property prevents K from containing uv. Because K is contained in (G \\ M) ⊔ edge v w and avoids uv, all edges of K belong to G \\ M'. Thus K can be transferred to a matching in G \\ M', showing ν(G \\ M') ≥ |K| > μ. Combined with the upper bound ν(G \\ M') ≤ μ + 1, this forces ν(G \\ M') = μ + 1.

    lines 289–299

    uses residual_matching_num_single_edge_exchange_iff_critical_uv_notin, residual_matching_num_single_edge_exchange_iff_critical_lower, residual_matching_num_single_edge_exchange_iff_critical_copy, le_iSup_of_le, le_rfl, lt_of_lt_of_le, residual_matching_num_single_edge_exchange_iff_critical_lt_succ_eq

          residual_matching_num_single_edge_exchange_iff_critical_uv_notin K hKmatch hu hvw hvwK
        have hKsub : K.edgeSet ⊆ (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})).edgeSet := by
          intro e he
          exact residual_matching_num_single_edge_exchange_iff_critical_lower hvw (K.edgeSet_subset he) (fun heuv => huvK (heuv ▸ he))
        obtain ⟨K', hK'match, hK'edge⟩ := residual_matching_num_single_edge_exchange_iff_critical_copy K hKmatch hKsub
        have hKle : K'.edgeSet.encard ≤ graph_matching_num (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})) :=
          le_iSup_of_le K' (le_iSup_of_le hK'match le_rfl)
        rw [hK'edge] at hKle
        have hlt2 : μ < graph_matching_num (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})) :=
          lt_of_lt_of_le hKencard hKle
        exact residual_matching_num_single_edge_exchange_iff_critical_lt_succ_eq hμtop hupper hlt2
SimpleGraph.Subgraph.mem_edgeSet
An unordered pair s(v, w) is in the edge set of a subgraph if and only if v and w are adjacent in the subgraph.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) is in the edge set of a graph if and only if v and w are adjacent in the graph.
Sym2.ind
Induction principle for unordered pairs Sym2: any property holding for all s(x, y) holds for all unordered pairs.
SimpleGraph.Subgraph.induce_verts
The vertex set of an induced subgraph is the inducing set of vertices.
SimpleGraph.Subgraph.mem_support
A vertex is in the support of a subgraph if and only if it is incident to some edge.
SimpleGraph.Subgraph.deleteEdges_adj
Vertices v and w are adjacent in the edge-deleted subgraph if and only if they were adjacent originally and the edge s(v, w) is not in the deleted set.
SimpleGraph.Subgraph.induce_adj
Vertices u and v are adjacent in an induced subgraph on s if and only if both belong to s and they were adjacent originally.
SimpleGraph.Subgraph.adj_symm
Adjacency in a subgraph is symmetric.
Set.mem_sdiff
An element x belongs to the set difference s \\ t if and only if x ∈ s and x ∉ t.
Sym2.eq_swap
An unordered pair is symmetric: s(a, b) = s(b, a).
residual_matching_num_single_edge_exchange_iff_critical_del
Deleting a set of edges T from a matching subgraph yields a matching subgraph with edge set E(N) \\ T.
SimpleGraph.support_subgraphOfAdj
The support of the single-edge subgraph of an adjacent pair uv is the pair {u, v}.
Set.disjoint_insert_right
A set s is disjoint from insert a t if and only if a ∉ s and s is disjoint from t.
Set.disjoint_singleton_right
A set s is disjoint from the singleton {a} if and only if a ∉ s.
Set.mem_singleton
An element a belongs to the singleton set {a}.
SimpleGraph.Subgraph.IsMatching.sup
The supremum of two matchings with disjoint supports is a matching.
SimpleGraph.Subgraph.IsMatching.subgraphOfAdj
The subgraph consisting of a single edge is a matching.
SimpleGraph.Subgraph.edgeSet_sup
The edge set of the supremum of two subgraphs is the union of their edge sets.
SimpleGraph.edgeSet_subgraphOfAdj
The edge set of the single-edge subgraph for an edge vw is the singleton {s(v, w)}.
Set.encard_union_eq
The extended cardinality of the union of disjoint sets is the sum of their extended cardinalities.
Set.encard_singleton
The extended cardinality of a singleton set is 1.
Set.encard_sdiff_add_encard_of_subset
If s ⊆ t, then |t \\ s| + |s| = |t| for extended cardinalities.
Set.encard_ne_top_iff
The extended cardinality of a set is not ∞ if and only if the set is finite.
Set.toFinite
A set whose subtype is finite is finite.
ne_top_of_le_ne_top
If a ≤ b and b ≠ ⊤, then a ≠ ⊤.
graph_matching_num_le_encard_edgeSet
The matching number of a graph is bounded by the extended cardinality of its edge set.
graph_matching_num_mono
If graph H is a subgraph of K, then the matching number of H is at most the matching number of K.
ENat.add_one_le_iff
For m ≠ ⊤ in ℕ∞, m + 1 ≤ n if and only if m < n.
le_antisymm
If a ≤ b and b ≤ a, then a = b.
SimpleGraph.edgeSet_edge
The edge set of the graph SimpleGraph.edge v w consists of the unordered pair s(v, w) minus the diagonal loops.
Set.mem_singleton_iff
An element a belongs to {b} if and only if a = b.
residual_matching_num_single_edge_exchange_iff_critical_copy
A matching subgraph whose edge set is contained in K can be copied into K as a matching with the same edge set.
le_iSup_of_le
If a ≤ f i for some index i, then a is bounded above by the supremum ⨆ j, f j.
le_rfl
Every element is less than or equal to itself: a ≤ a.
False.elim
From False, any proposition follows.
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
le_self_add
In a canonically ordered additive monoid, a ≤ a + b.
SimpleGraph.edgeSet_deleteEdges
The edge set of G.deleteEdges s is G.edgeSet \\ s.
Sym2.mk_isDiag_iff
An unordered pair s(x, y) is on the diagonal (a self-loop) if and only if x = y.
residual_matching_num_single_edge_exchange_iff_critical_replace
Removing edge vw from matching M and adding edge uv with unsaturated u produces a valid matching with edge set (E(M) \\ {vw}) ∪ {uv}.
residual_matching_num_single_edge_exchange_iff_critical_card
Replacing one element in a set with a non-element preserves extended cardinality: |(E \\ {a}) ∪ {b}| = |E|.
residual_matching_num_single_edge_exchange_iff_critical_num_ne_top
The matching number of a graph on a finite vertex type is finite.
ENat.lt_add_one_iff
For n ≠ ⊤ in ℕ∞, m < n + 1 if and only if m ≤ n.
residual_matching_num_single_edge_exchange_iff_critical_num_mono
Monotonicity of matching number under inclusion of edge sets.
residual_matching_num_single_edge_exchange_iff_critical_upper
The residual graph after exchanging vw for uv is an edge subgraph of (G \\ M) + vw.
residual_matching_num_single_edge_exchange_iff_critical_one_edge
Adding a single edge to any graph increases the matching number by at most 1.
residual_matching_num_single_edge_exchange_iff_critical_lt_succ_eq
For a ≠ ⊤, if b ≤ a + 1 and a < b, then b = a + 1.
lt_iSup_iff
Strict inequality below a supremum: a < ⨆ i, f i if and only if a < f i for some index i.
lt_irrefl
Strict inequality is irreflexive: ¬(a < a).
lt_of_le_of_lt
Transitivity combining ≤ and <: if a ≤ b and b < c, then a < c.
residual_matching_num_single_edge_exchange_iff_critical_uv_notin
Any matching containing vw cannot contain uv when u is not in M and w is in M.
residual_matching_num_single_edge_exchange_iff_critical_lower
Any edge of (G \\ M) + vw distinct from uv belongs to G \\ M'.
lt_of_lt_of_le
Transitivity combining < and ≤: if a < b and b ≤ c, then a < c.

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 Sym2lemma residual_matching_num_single_edge_exchange_iff_critical_copy    {V : Type*} {H K : SimpleGraph V} (N : H.Subgraph) (hN : N.IsMatching)    (h : N.edgeSet ⊆ K.edgeSet) :    ∃ N' : K.Subgraph, N'.IsMatching ∧ N'.edgeSet = N.edgeSet := by  let N' : K.Subgraph :=    { verts := N.verts      Adj := N.Adj      adj_sub := by        intro x y hxy        have hmem : s(x, y) ∈ K.edgeSet := h (by rwa [SimpleGraph.Subgraph.mem_edgeSet])        rwa [SimpleGraph.mem_edgeSet] at hmem      edge_vert := by        intro x y hxy        exact N.edge_vert hxy      symm := N.symm }  refine ⟨N', hN, ?_⟩  ext e  induction e using Sym2.ind with  | _ x y => rw [SimpleGraph.Subgraph.mem_edgeSet, SimpleGraph.Subgraph.mem_edgeSet]lemma residual_matching_num_single_edge_exchange_iff_critical_del    {V : Type*} {H : SimpleGraph V} {N : H.Subgraph} (hN : N.IsMatching)    (T : Set (Sym2 V)) :    ∃ N' : H.Subgraph, N'.IsMatching ∧ N'.edgeSet = N.edgeSet \ T := by  refine ⟨(N.deleteEdges T).induce (N.deleteEdges T).support, ?_, ?_⟩  · intro x hx    rw [SimpleGraph.Subgraph.induce_verts, SimpleGraph.Subgraph.mem_support] at hx    obtain ⟨y, hxy⟩ := hx    rw [SimpleGraph.Subgraph.deleteEdges_adj] at hxy    refine ⟨y, ?_, ?_⟩    · change ((N.deleteEdges T).induce (N.deleteEdges T).support).Adj x y      rw [SimpleGraph.Subgraph.induce_adj, SimpleGraph.Subgraph.deleteEdges_adj]      refine ⟨by rw [SimpleGraph.Subgraph.mem_support]; exact ⟨y, hxy⟩, ?_, hxy⟩      rw [SimpleGraph.Subgraph.mem_support]; exact ⟨x, SimpleGraph.Subgraph.adj_symm _ hxy⟩    · intro z hz      rw [SimpleGraph.Subgraph.induce_adj, SimpleGraph.Subgraph.deleteEdges_adj] at hz      exact (hN hxy.1.fst_mem).unique hz.2.2.1 hxy.1  · ext e    refine Sym2.ind (fun x y => ?_) e    rw [SimpleGraph.Subgraph.mem_edgeSet, SimpleGraph.Subgraph.induce_adj,        SimpleGraph.Subgraph.deleteEdges_adj, Set.mem_sdiff, SimpleGraph.Subgraph.mem_edgeSet]    simp only [SimpleGraph.Subgraph.mem_support]    constructor    · rintro ⟨_, _, h, hT⟩; exact ⟨h, hT⟩    · rintro ⟨h, hT⟩      refine ⟨⟨y, ?_⟩, ⟨x, ?_⟩, h, hT⟩      · rw [SimpleGraph.Subgraph.deleteEdges_adj]; exact ⟨h, hT⟩      · rw [SimpleGraph.Subgraph.deleteEdges_adj]; exact ⟨SimpleGraph.Subgraph.adj_symm N h, by rwa [Sym2.eq_swap]⟩lemma residual_matching_num_single_edge_exchange_iff_critical_replace    {V : Type*} {G : SimpleGraph V} {M : G.Subgraph}    (hM : M.IsMatching) {u v w : V} (hu : u ∉ M.verts) (hvw : M.Adj v w) (huv : G.Adj u v) :    ∃ M' : G.Subgraph, M'.IsMatching ∧ M'.edgeSet = (M.edgeSet \ {s(v, w)}) ∪ {s(u, v)} := by  obtain ⟨D, hDmatch, hDedge⟩ := residual_matching_num_single_edge_exchange_iff_critical_del hM {s(v, w)}  have hdisj : Disjoint D.support (G.subgraphOfAdj huv).support := by    rw [SimpleGraph.support_subgraphOfAdj]    rw [Set.disjoint_insert_right, Set.disjoint_singleton_right]    constructor    · intro huD      have : D.support ⊆ M.verts := by        intro x hx        rw [SimpleGraph.Subgraph.mem_support] at hx        obtain ⟨y, hy⟩ := hx        have : s(x, y) ∈ D.edgeSet := by rwa [SimpleGraph.Subgraph.mem_edgeSet]        rw [hDedge] at this        have hMadj : M.Adj x y := by          have := this.1          rwa [SimpleGraph.Subgraph.mem_edgeSet] at this        exact hMadj.fst_mem      exact hu (this huD)    · intro hvD      rw [SimpleGraph.Subgraph.mem_support] at hvD      obtain ⟨z, hz⟩ := hvD      have : s(v, z) ∈ D.edgeSet := by rwa [SimpleGraph.Subgraph.mem_edgeSet]      rw [hDedge, Set.mem_sdiff, SimpleGraph.Subgraph.mem_edgeSet] at this      have hMadj : M.Adj v z := this.1      have hnot : s(v, z) ∉ ({s(v, w)} : Set (Sym2 V)) := this.2      have hz_eq_w : z = w := (hM hvw.fst_mem).unique hMadj hvw      subst hz_eq_w      exact hnot (Set.mem_singleton _)  refine ⟨D ⊔ G.subgraphOfAdj huv, ?_, ?_⟩  · exact SimpleGraph.Subgraph.IsMatching.sup hDmatch (SimpleGraph.Subgraph.IsMatching.subgraphOfAdj huv) hdisj  · rw [SimpleGraph.Subgraph.edgeSet_sup, hDedge, SimpleGraph.edgeSet_subgraphOfAdj]lemma residual_matching_num_single_edge_exchange_iff_critical_card    {α : Type*} (E : Set α) {a b : α} (ha : a ∈ E) (hb : b ∉ E) :    ((E \ {a}) ∪ {b}).encard = E.encard := by  have hd : Disjoint (E \ {a}) ({b} : Set α) := by    rw [Set.disjoint_singleton_right]    rintro ⟨h, -⟩    exact hb h  rw [Set.encard_union_eq hd, Set.encard_singleton, ← Set.encard_sdiff_add_encard_of_subset (Set.singleton_subset_iff.mpr ha), Set.encard_singleton]lemma residual_matching_num_single_edge_exchange_iff_critical_num_ne_top    {V : Type*} [Fintype V] (H : SimpleGraph V) :    graph_matching_num H ≠ ⊤ := by  have : H.edgeSet.encard ≠ ⊤ := by    rw [Set.encard_ne_top_iff]    exact Set.toFinite H.edgeSet  exact ne_top_of_le_ne_top this (graph_matching_num_le_encard_edgeSet H)lemma residual_matching_num_single_edge_exchange_iff_critical_num_mono    {V : Type*} {H K : SimpleGraph V} (h : H.edgeSet ⊆ K.edgeSet) :    graph_matching_num H ≤ graph_matching_num K := by  apply graph_matching_num_mono  intro x y hxy  have : s(x, y) ∈ K.edgeSet := h (by rwa [SimpleGraph.mem_edgeSet])  rwa [SimpleGraph.mem_edgeSet] at thislemma residual_matching_num_single_edge_exchange_iff_critical_lt_succ_eq    {a b : ℕ∞} (ha : a ≠ ⊤) (h1 : b ≤ a + 1) (h2 : a < b) : b = a + 1 := by  have : a + 1 ≤ b := (ENat.add_one_le_iff ha).mpr h2  exact le_antisymm h1 thislemma residual_matching_num_single_edge_exchange_iff_critical_one_edge    {V : Type*} (H : SimpleGraph V) (u v : V) :    graph_matching_num (H ⊔ SimpleGraph.edge u v) ≤ graph_matching_num H + 1 := by  unfold graph_matching_num  apply iSup_le  intro N  apply iSup_le  intro hN  by_cases hmem : s(u, v) ∈ N.edgeSet  · obtain ⟨N0, hN0match, hN0edge⟩ := residual_matching_num_single_edge_exchange_iff_critical_del hN {s(u, v)}    have hsub : N0.edgeSet ⊆ H.edgeSet := by      rw [hN0edge]      intro e he      have heN : e ∈ (H ⊔ SimpleGraph.edge u v).edgeSet := N.edgeSet_subset he.1      rw [SimpleGraph.edgeSet_sup, Set.mem_union] at heN      rcases heN with heH | heE      · exact heH      · rw [SimpleGraph.edgeSet_edge] at heE        exfalso        exact he.2 (Set.mem_singleton_iff.mpr heE.1)    obtain ⟨N', hN'match, hN'edge⟩ := residual_matching_num_single_edge_exchange_iff_critical_copy N0 hN0match hsub    have hle : N'.edgeSet.encard ≤ ⨆ (M : H.Subgraph) (_ : M.IsMatching), M.edgeSet.encard :=      le_iSup_of_le N' (le_iSup_of_le hN'match le_rfl)    have heq : N.edgeSet.encard = N0.edgeSet.encard + 1 := by      rw [hN0edge]      have hsing : ({s(u, v)} : Set (Sym2 V)).encard = 1 := Set.encard_singleton _      rw [← hsing]      exact (Set.encard_sdiff_add_encard_of_subset (Set.singleton_subset_iff.mpr hmem)).symm    rw [heq, ← hN'edge]    gcongr  · have hsub : N.edgeSet ⊆ H.edgeSet := by      intro e he      have heN : e ∈ (H ⊔ SimpleGraph.edge u v).edgeSet := N.edgeSet_subset he      rw [SimpleGraph.edgeSet_sup, Set.mem_union] at heN      rcases heN with heH | heE      · exact heH      · rw [SimpleGraph.edgeSet_edge] at heE        have : e = s(u, v) := heE.1        subst this        exact False.elim (hmem he)    obtain ⟨N', hN'match, hN'edge⟩ := residual_matching_num_single_edge_exchange_iff_critical_copy N hN hsub    have hle : N'.edgeSet.encard ≤ ⨆ (M : H.Subgraph) (_ : M.IsMatching), M.edgeSet.encard :=      le_iSup_of_le N' (le_iSup_of_le hN'match le_rfl)    rw [← hN'edge]    exact le_trans hle le_self_addlemma residual_matching_num_single_edge_exchange_iff_critical_upper    {V : Type*} {G : SimpleGraph V} {M : G.Subgraph} {v w u : V}    (hvw : M.Adj v w) :    (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})).edgeSet ⊆      ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w).edgeSet := by  intro e he  rw [SimpleGraph.edgeSet_deleteEdges, Set.mem_sdiff] at he  rw [SimpleGraph.edgeSet_sup, Set.mem_union, SimpleGraph.edgeSet_deleteEdges, Set.mem_sdiff]  by_cases hevw : e = s(v, w)  · right    subst hevw    rw [SimpleGraph.edgeSet_edge, Set.mem_sdiff, Set.mem_singleton_iff]    refine ⟨rfl, ?_⟩    intro hd    exact hvw.ne (Sym2.mk_isDiag_iff.mp hd)  · left    refine ⟨he.1, ?_⟩    intro heM    have : e ∈ (M.edgeSet \ {s(v, w)}) ∪ {s(u, v)} := by      left      exact ⟨heM, hevw⟩    exact he.2 thislemma residual_matching_num_single_edge_exchange_iff_critical_lower    {V : Type*} {G : SimpleGraph V} {M : G.Subgraph} {v w u : V}    (hvw : M.Adj v w) {e : Sym2 V}    (heH : e ∈ ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w).edgeSet)    (hne : e ≠ s(u, v)) :    e ∈ (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})).edgeSet := by  rw [SimpleGraph.edgeSet_sup, Set.mem_union, SimpleGraph.edgeSet_deleteEdges, Set.mem_sdiff] at heH  rw [SimpleGraph.edgeSet_deleteEdges, Set.mem_sdiff, Set.mem_union, Set.mem_singleton_iff]  rcases heH with ⟨heG, heM⟩ | heE  · refine ⟨heG, ?_⟩    rintro (⟨heM2, -⟩ | rfl)    · exact heM heM2    · exact hne rfl  · rw [SimpleGraph.edgeSet_edge, Set.mem_sdiff, Set.mem_singleton_iff] at heE    have he_eq : e = s(v, w) := heE.1    subst he_eq    have hvwG : s(v, w) ∈ G.edgeSet := by      rw [SimpleGraph.mem_edgeSet]      exact M.adj_sub hvw    refine ⟨hvwG, ?_⟩    rintro (⟨-, hnot⟩ | h_eq)    · exact hnot rfl    · exact hne h_eqlemma residual_matching_num_single_edge_exchange_iff_critical_uv_notin    {V : Type*} {G : SimpleGraph V} {M : G.Subgraph}    {H : SimpleGraph V} (K : H.Subgraph) (hK : K.IsMatching)    {u v w : V} (hu : u ∉ M.verts) (hvw : M.Adj v w)    (hvwK : s(v, w) ∈ K.edgeSet) :    s(u, v) ∉ K.edgeSet := by  intro huvK  have hKvw : K.Adj v w := by rwa [SimpleGraph.Subgraph.mem_edgeSet] at hvwK  have hKuv : K.Adj u v := by rwa [SimpleGraph.Subgraph.mem_edgeSet] at huvK  have hKvu : K.Adj v u := SimpleGraph.Subgraph.adj_symm K hKuv  have hu_eq_w : u = w := (hK hKvw.fst_mem).unique hKvu hKvw  subst hu_eq_w  exact hu hvw.snd_mem/-- Residual matching number increases under single-edge exchange if and only if the exchanged edge is critical. -/theorem residual_matching_num_single_edge_exchange_iff_critical {V : Type*} [Fintype V]    (G : SimpleGraph V) (M : G.Subgraph) (hM : graph_is_maximum_matching G M)    (u v w : V) (hu : u ∉ M.verts) (hvw : M.Adj v w) (huv : G.Adj u v) :    ∃ M' : G.Subgraph,      M'.edgeSet = (M.edgeSet \ {s(v, w)}) ∪ {s(u, v)} ∧      graph_is_maximum_matching G M' ∧      (graph_matching_num (G.deleteEdges M'.edgeSet) =          graph_matching_num (G.deleteEdges M.edgeSet) + 1 ↔        graph_matching_num ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w) =          graph_matching_num (G.deleteEdges M.edgeSet) + 1) := by  obtain ⟨hMmatch, hMcard⟩ := hM  have hbE : s(u, v) ∉ M.edgeSet := fun h =>    hu (M.edge_vert (by rwa [SimpleGraph.Subgraph.mem_edgeSet] at h))  obtain ⟨M', hM'match, hM'edge⟩ :=    residual_matching_num_single_edge_exchange_iff_critical_replace hMmatch hu hvw huv  have hM'card : graph_is_maximum_matching G M' := by    refine ⟨hM'match, ?_⟩    rw [hM'edge, residual_matching_num_single_edge_exchange_iff_critical_card M.edgeSet (by rw [SimpleGraph.Subgraph.mem_edgeSet]; exact hvw) hbE,      hMcard]  refine ⟨M', hM'edge, hM'card, ?_⟩  rw [hM'edge]  set μ := graph_matching_num (G.deleteEdges M.edgeSet)  have hμtop : μ ≠ ⊤ := residual_matching_num_single_edge_exchange_iff_critical_num_ne_top _  have hone : μ < μ + 1 := (ENat.lt_add_one_iff hμtop).mpr le_rfl  have hupper : graph_matching_num (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})) ≤ μ + 1 :=    le_trans      (residual_matching_num_single_edge_exchange_iff_critical_num_mono (residual_matching_num_single_edge_exchange_iff_critical_upper hvw))      (residual_matching_num_single_edge_exchange_iff_critical_one_edge _ v w)  have hHup : graph_matching_num ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w) ≤ μ + 1 :=    residual_matching_num_single_edge_exchange_iff_critical_one_edge _ v w  constructor  · intro h    refine residual_matching_num_single_edge_exchange_iff_critical_lt_succ_eq hμtop hHup ?_    calc μ < μ + 1 := hone      _ = graph_matching_num (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})) := h.symm      _ ≤ graph_matching_num ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w) :=        residual_matching_num_single_edge_exchange_iff_critical_num_mono (residual_matching_num_single_edge_exchange_iff_critical_upper hvw)  · intro h    have hlt : μ < graph_matching_num ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w) := by      rw [h]      exact hone    unfold graph_matching_num at hlt    rw [lt_iSup_iff] at hlt    obtain ⟨K, hK⟩ := hlt    rw [lt_iSup_iff] at hK    obtain ⟨hKmatch, hKencard⟩ := hK    have hvwK : s(v, w) ∈ K.edgeSet := by      by_contra hnot      have hsub : K.edgeSet ⊆ (G.deleteEdges M.edgeSet).edgeSet := by        intro e he        have heH : e ∈ ((G.deleteEdges M.edgeSet) ⊔ SimpleGraph.edge v w).edgeSet := K.edgeSet_subset he        rw [SimpleGraph.edgeSet_sup, Set.mem_union] at heH        rcases heH with he1 | he2        · exact he1        · rw [SimpleGraph.edgeSet_edge] at he2          have : e = s(v, w) := he2.1          subst this          exact False.elim (hnot he)      obtain ⟨K', hK'match, hK'edge⟩ := residual_matching_num_single_edge_exchange_iff_critical_copy K hKmatch hsub      have hle : K'.edgeSet.encard ≤ μ :=        le_iSup_of_le K' (le_iSup_of_le hK'match le_rfl)      rw [hK'edge] at hle      exact lt_irrefl _ (lt_of_le_of_lt hle hKencard)    have huvK : s(u, v) ∉ K.edgeSet :=      residual_matching_num_single_edge_exchange_iff_critical_uv_notin K hKmatch hu hvw hvwK    have hKsub : K.edgeSet ⊆ (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})).edgeSet := by      intro e he      exact residual_matching_num_single_edge_exchange_iff_critical_lower hvw (K.edgeSet_subset he) (fun heuv => huvK (heuv ▸ he))    obtain ⟨K', hK'match, hK'edge⟩ := residual_matching_num_single_edge_exchange_iff_critical_copy K hKmatch hKsub    have hKle : K'.edgeSet.encard ≤ graph_matching_num (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})) :=      le_iSup_of_le K' (le_iSup_of_le hK'match le_rfl)    rw [hK'edge] at hKle    have hlt2 : μ < graph_matching_num (G.deleteEdges ((M.edgeSet \ {s(v, w)}) ∪ {s(u, v)})) :=      lt_of_lt_of_le hKencard hKle    exact residual_matching_num_single_edge_exchange_iff_critical_lt_succ_eq hμtop hupper hlt2
See it in the graphDiscuss this resultChallenge it