residual_matching_num_single_edge_exchange_iff_critical
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.
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.
uses
SimpleGraph.Subgraph.mem_edgeSet,SimpleGraph.mem_edgeSet,Sym2.indlet 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]
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.
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_swaprefine ⟨(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]⟩
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.
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_subgraphOfAdjobtain ⟨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]
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|.
uses
Set.disjoint_singleton_right,Set.encard_union_eq,Set.encard_singleton,Set.encard_sdiff_add_encard_of_subsethave 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]
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.
uses
Set.encard_ne_top_iff,Set.toFinite,ne_top_of_le_ne_top,graph_matching_num_le_encard_edgeSethave : 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)
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).
uses
graph_matching_num_mono,SimpleGraph.mem_edgeSetapply 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
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.
uses
ENat.add_one_le_iff,le_antisymmhave : a + 1 ≤ b := (ENat.add_one_le_iff ha).mpr h2 exact le_antisymm h1 this
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.
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_addunfold 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
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.
uses
SimpleGraph.edgeSet_deleteEdges,Set.mem_sdiff,SimpleGraph.edgeSet_sup,Set.mem_union,SimpleGraph.edgeSet_edge,Set.mem_singleton_iff,Sym2.mk_isDiag_iffintro 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
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'.
uses
SimpleGraph.edgeSet_sup,Set.mem_union,SimpleGraph.edgeSet_deleteEdges,Set.mem_sdiff,Set.mem_singleton_iff,SimpleGraph.edgeSet_edge,SimpleGraph.mem_edgeSetrw [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
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.
uses
SimpleGraph.Subgraph.mem_edgeSet,SimpleGraph.Subgraph.adj_symms(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
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.
uses
SimpleGraph.Subgraph.mem_edgeSet,residual_matching_num_single_edge_exchange_iff_critical_replace,residual_matching_num_single_edge_exchange_iff_critical_cardobtain ⟨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, ?_⟩
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.
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_edgerw [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
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.
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_upperconstructor · 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
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.
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_lthave 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 :=
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.
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_eqresidual_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
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 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