bipartite_well_covered_has_perfect_matching
Every finite connected well-covered bipartite graph G with at least 2 vertices has a perfect matching.
Statement
theorem bipartite_well_covered_has_perfect_matching {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (hbip : G.IsBipartite) (hcard : 2 ≤ Fintype.card V) (hwc : simple_graph_is_well_covered G) : ∃ M : SimpleGraph.Subgraph G, M.IsPerfectMatching
- Source
- step towards bipartite_well_covered_exists_perfect_matching_ravindra
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_is_well_coveredA finite graph is well-covered if all its maximal independent sets have the same cardinality (equivalently, all its minimal vertex covers…
- Arena.Reachable.transReachability is transitive.
- Used by 1
- bipartite_well_covered_exists_perfect_matching_ravindraEvery finite connected well-covered bipartite graph G with at least 2 vertices has a perfect matching M such that for every edge uv of M,…
The proof, explained
The theorem is proved by verifying Hall's marriage condition for a perfect matching: for every subset of vertices s, its neighborhood satisfies |s| ≤ |N(s)|. Since G is connected and has at least two vertices, its two bipartite parts A and B are maximal independent sets, so well-coveredness implies |A| = |B| and every maximal independent set has size |A|. A helper lemma shows that any subset t ⊆ A has |t| ≤ |N(t)| by extending t ∪ (B \ N(t)) to a maximal independent set J of size |A| = |B|. Finally, any s ⊆ V is split into s ∩ A and s ∩ B, and applying the helper lemma to both sides yields |s| ≤ |N(s)|.
The neighborhood N(t) of any subset t ⊆ A is contained in B.
Let y be in the neighborhood of t, so y is adjacent to some x ∈ t. Since G is bipartite between A and B, the edge between x and y must connect A and B. Because t ⊆ A and A is disjoint from B, x must be in A, which forces y ∈ B.
uses
Set.mem_iUnion,SimpleGraph.mem_neighborSet,Set.disjoint_left.mpclassical set N : Set V := ⋃ x ∈ t, G.neighborSet x with hNdef have hNsub : N ⊆ B := by intro y hy simp only [hNdef, Set.mem_iUnion, exists_prop] at hy obtain ⟨x, hxt, hyx⟩ := hy rw [SimpleGraph.mem_neighborSet] at hyx rcases hAB.mem_of_adj hyx with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact h2 · exact absurd h1 (Set.disjoint_left.mp hAB.disjoint (ht hxt))
The set t ∪ (B \ N) is an independent set in G.
Vertices in t have no edges between them because t ⊆ A and A is independent. Vertices in B \ N have no edges between them because B is independent. Furthermore, there are no edges between t and B \ N because, by definition, any neighbor of t in B belongs to N.
uses
SimpleGraph.mem_neighborSet,Set.mem_iUnionhave hIind : G.IsIndepSet (t ∪ (B \ N)) := by intro a ha b hb hab hadj rcases ha with ha | ⟨haB, haN⟩ · rcases hb with hb | ⟨hbB, hbN⟩ · exact hAind (ht ha) (ht hb) hab hadj · refine hbN ?_ simp only [hNdef, Set.mem_iUnion, exists_prop] exact ⟨a, ha, by rwa [SimpleGraph.mem_neighborSet]⟩ · rcases hb with hb | ⟨hbB, hbN⟩ · refine haN ?_ simp only [hNdef, Set.mem_iUnion, exists_prop] exact ⟨b, hb, by rw [SimpleGraph.mem_neighborSet]; exact hadj.symm⟩ · exact hBind haB hbB hab hadj
There exists a maximal independent set J containing t ∪ (B \ N), and |J| = |A|.
Since V is finite, the collection of independent supersets of t ∪ (B \ N) is finite and nonempty, hence possesses a maximal element J. This J is maximal among all independent sets of G. By the well-coveredness assumption that all maximal independent sets have the same cardinality as A, we have |J| = |A|.
uses
Set.toFinite,subset_refl,Set.Subset.transhave hSfin : {u : Set V | (t ∪ (B \ N)) ⊆ u ∧ G.IsIndepSet u}.Finite := Set.toFinite _ obtain ⟨J, hJ⟩ := hSfin.exists_maximal ⟨t ∪ (B \ N), subset_refl _, hIind⟩ have hJmax : Maximal G.IsIndepSet J := by refine ⟨hJ.1.2, ?_⟩ intro u hu hJu exact hJ.2 ⟨Set.Subset.trans hJ.1.1 hJu, hu⟩ hJu have hJcard : J.ncard = A.ncard := hAmax J hJmax
|t| ≤ |N(t)|.
Because t and B \ N are disjoint subsets of J, we have |t| + |B \ N| = |t ∪ (B \ N)| ≤ |J| = |A|. Since N ⊆ B, |B \ N| = |B| - |N|. Using the hypothesis |A| = |B|, this gives |t| + |B| - |N| ≤ |B|, which simplifies to |t| ≤ |N|.
uses
Set.ncard_le_ncard,Set.disjoint_left,Set.disjoint_left.mp,Set.ncard_sdiff,Set.ncard_union_eqhave hIle : (t ∪ (B \ N)).ncard ≤ J.ncard := Set.ncard_le_ncard hJ.1.1 have hdisj : Disjoint t (B \ N) := by rw [Set.disjoint_left] intro x hx hx' exact Set.disjoint_left.mp hAB.disjoint (ht hx) hx'.1 have hNleB : N.ncard ≤ B.ncard := Set.ncard_le_ncard hNsub have hBN : (B \ N).ncard = B.ncard - N.ncard := Set.ncard_sdiff hNsub have hIunion : (t ∪ (B \ N)).ncard = t.ncard + (B \ N).ncard := Set.ncard_union_eq hdisj omega
The 2-coloring yields a valid bipartition V = A ∪ B with A and B independent.
From the bipartite assumption, we obtain a 2-coloring C : V → Fin 2. Defining A = C⁻¹(0) and B = C⁻¹(1), these sets are disjoint, independent, and partition V since every color is 0 or 1. Every edge of G connects a vertex in A and a vertex in B.
uses
Set.toFinite,Set.disjoint_left,Or.inl,Or.inr,Set.univ,iff_trueclassical haveI : G.LocallyFinite := fun v => (Set.toFinite _).fintype obtain ⟨C⟩ := hbip have htwo : ∀ x : Fin 2, x = 0 ∨ x = 1 := fun x => by fin_cases x <;> simp set A : Set V := C.colorClass 0 with hAdef set B : Set V := C.colorClass 1 with hBdef have hAB : G.IsBipartiteWith A B := by refine ⟨?_, ?_⟩ · rw [Set.disjoint_left] intro x hx hx' exact absurd (hx.symm.trans hx') (by decide) · intro v w hvw have hne := C.valid hvw have hv := htwo (C v) have hw := htwo (C w) rcases hv with h | h · refine Or.inl ⟨h, ?_⟩ rcases hw with h' | h' · exact absurd (h.trans h'.symm) hne · exact h' · refine Or.inr ⟨h, ?_⟩ rcases hw with h' | h' · exact h' · exact absurd (h.trans h'.symm) hne have hAind : G.IsIndepSet A := C.isIndepSet_colorClass 0 have hBind : G.IsIndepSet B := C.isIndepSet_colorClass 1 have hunion : A ∪ B = Set.univ := by ext v simp only [Set.mem_union, Set.mem_univ, iff_true] exact htwo (C v)
Every vertex in G has degree at least 1.
Because |V| ≥ 2, every vertex v has some distinct vertex w ≠ v. Since G is connected, there exists a path from v to w; the first step along this path gives a neighbor of v.
uses
Fintype.card_le_one_iff.mprhave hne : ∀ v : V, ∃ w, G.Adj v w := by intro v obtain ⟨w, hw⟩ : ∃ w, w ≠ v := by by_contra h push Not at h have : Fintype.card V ≤ 1 := Fintype.card_le_one_iff.mpr fun a b => by rw [h a, h b] omega have hr : G.Reachable v w := hconn.preconnected v w exact hr.elim fun p => by cases p with | nil => exact absurd rfl hw | cons h _ => exact ⟨_, h⟩
The independent sets A and B are both maximal independent sets in G.
In a bipartite graph whose parts cover V and where every vertex has degree at least 1, each part is a maximal independent set: adding any vertex x from the other side introduces an edge between x and its neighbor, which must lie in the first part.
uses
SimpleGraph.isMaximalIndepSet_iff,Set.union_commhave maxim : ∀ (P Q : Set V), G.IsBipartiteWith P Q → G.IsIndepSet P → P ∪ Q = Set.univ → Maximal G.IsIndepSet P := by intro P Q hPQ hPind hPQun rw [SimpleGraph.isMaximalIndepSet_iff] refine ⟨hPind, ?_⟩ intro u hu hPu x hx by_contra hxP have hxQ : x ∈ Q := by have h : x ∈ P ∪ Q := by rw [hPQun]; trivial exact h.resolve_left hxP obtain ⟨w, hxw⟩ := hne x have hwP : w ∈ P := by rcases hPQ.mem_of_adj hxw with ⟨h1, -⟩ | ⟨-, h2⟩ · exact absurd h1 hxP · exact h2 exact hu hx (hPu hwP) hxw.ne hxw have hAmaxS : Maximal G.IsIndepSet A := maxim A B hAB hAind hunion have hBmaxS : Maximal G.IsIndepSet B := by refine maxim B A hAB.symm hBind ?_ rw [Set.union_comm]; exact hunion
All maximal independent sets have the same size, so |A| = |B|.
Translating the well-coveredness property from Finset to Set shows that any two maximal independent sets have equal cardinality. Since A and B are maximal independent sets, |A| = |B|, and every maximal independent set has size |A| and |B|.
uses
Set.toFinite,Set.Finite.coe_toFinset,Set.Finite.mem_toFinset,Set.ncard_eq_toFinset_cardhave hwcS : ∀ s t : Set V, Maximal G.IsIndepSet s → Maximal G.IsIndepSet t → s.ncard = t.ncard := by intro s t hs ht have hsfin : s.Finite := Set.toFinite s have htfin : t.Finite := Set.toFinite t have key : ∀ (u : Set V), (hufin : u.Finite) → Maximal G.IsIndepSet u → Maximal (fun v : Finset V => G.IsIndepSet (↑v : Set V)) hufin.toFinset := by intro u hufin hu have hcoe : (↑hufin.toFinset : Set V) = u := Set.Finite.coe_toFinset hufin refine ⟨?_, ?_⟩ · show G.IsIndepSet (↑hufin.toFinset : Set V) rw [hcoe]; exact hu.1 · intro w hw huw have h1 : u ⊆ (↑w : Set V) := by rw [← hcoe]; exact huw have h2 : (↑w : Set V) ⊆ u := hu.2 hw h1 intro y hy rw [Set.Finite.mem_toFinset] exact h2 hy have h1 := key s hsfin hs have h2 := key t htfin ht have h := hwc hsfin.toFinset htfin.toFinset h1 h2 rw [Set.ncard_eq_toFinset_card s hsfin, Set.ncard_eq_toFinset_card t htfin] exact h have hcardAB : A.ncard = B.ncard := hwcS A B hAmaxS hBmaxS have hAmax : ∀ s : Set V, Maximal G.IsIndepSet s → s.ncard = A.ncard := fun s hs => hwcS s A hs hAmaxS have hBmax : ∀ s : Set V, Maximal G.IsIndepSet s → s.ncard = B.ncard := fun s hs => hwcS s B hs hBmaxS
Hall's condition reduces to decomposing N(s) into disjoint neighborhoods N(s ∩ A) ⊆ B and N(s ∩ B) ⊆ A.
By Hall's Marriage Theorem for bipartite graphs, it suffices to show |s| ≤ |N(s)| for all s ⊆ V. Any vertex x ∈ s belongs to either A or B, so N(s) is the union of N(s ∩ A) and N(s ∩ B). Since G is bipartite between A and B, N(s ∩ A) ⊆ B and N(s ∩ B) ⊆ A, making these two neighborhood sets disjoint.
uses
SimpleGraph.exists_isPerfectMatching_of_forall_ncard_le,Set.mem_iUnion,SimpleGraph.mem_neighborSet,Set.disjoint_left,Set.disjoint_left.mprefine SimpleGraph.exists_isPerfectMatching_of_forall_ncard_le hAB ?_ intro s have hdecomp : (⋃ x ∈ s, G.neighborSet x) = (⋃ x ∈ s ∩ A, G.neighborSet x) ∪ (⋃ x ∈ s ∩ B, G.neighborSet x) := by ext y simp only [Set.mem_iUnion, Set.mem_inter_iff, Set.mem_union, exists_prop] constructor · rintro ⟨x, hx, hy⟩ rcases htwo (C x) with h | h · exact Or.inl ⟨x, ⟨hx, h⟩, hy⟩ · exact Or.inr ⟨x, ⟨hx, h⟩, hy⟩ · rintro (⟨x, ⟨hx, -⟩, hy⟩ | ⟨x, ⟨hx, -⟩, hy⟩) · exact ⟨x, hx, hy⟩ · exact ⟨x, hx, hy⟩ have hNdisj : Disjoint (⋃ x ∈ s ∩ A, G.neighborSet x) (⋃ x ∈ s ∩ B, G.neighborSet x) := by rw [Set.disjoint_left] intro y hy hy' simp only [Set.mem_iUnion, Set.mem_inter_iff, exists_prop] at hy hy' obtain ⟨x, ⟨-, hx0⟩, hyx⟩ := hy obtain ⟨x', ⟨-, hx1⟩, hyx'⟩ := hy' rw [SimpleGraph.mem_neighborSet] at hyx hyx' have hy1 : y ∈ B := by rcases hAB.mem_of_adj hyx with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact h2 · exact absurd h1 (Set.disjoint_left.mp hAB.disjoint hx0) have hy0 : y ∈ A := by rcases hAB.mem_of_adj hyx' with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 (Set.disjoint_right.mp hAB.disjoint hx1) · exact h2 exact Set.disjoint_left.mp hAB.disjoint hy0 hy1
|s| ≤ |N(s)| for all s ⊆ V, establishing the existence of a perfect matching.
Since s is the disjoint union of s ∩ A and s ∩ B, |s| = |s ∩ A| + |s ∩ B|. Applying the helper lemma to s ∩ A ⊆ A and s ∩ B ⊆ B gives |s ∩ A| ≤ |N(s ∩ A)| and |s ∩ B| ≤ |N(s ∩ B)|. Summing these inequalities yields |s| ≤ |N(s)|, which completes the Hall condition.
uses
Set.inter_union_distrib_left,Set.inter_univ,Set.disjoint_left,bipartite_well_covered_has_perfect_matching_hall_side,Set.inter_subset_right,Set.ncard_union_eqhave hsdecomp : s = (s ∩ A) ∪ (s ∩ B) := by rw [← Set.inter_union_distrib_left, hunion, Set.inter_univ] have hsdisj : Disjoint (s ∩ A) (s ∩ B) := by rw [Set.disjoint_left] intro x hx hx' exact Set.disjoint_left.mp hAB.disjoint hx.2 hx'.2 have h1 : (s ∩ A).ncard ≤ (⋃ x ∈ s ∩ A, G.neighborSet x).ncard := bipartite_well_covered_has_perfect_matching_hall_side hAB hAind hBind hAmax hcardAB _ Set.inter_subset_right have h2 : (s ∩ B).ncard ≤ (⋃ x ∈ s ∩ B, G.neighborSet x).ncard := bipartite_well_covered_has_perfect_matching_hall_side hAB.symm hBind hAind hBmax hcardAB.symm _ Set.inter_subset_right have hs_card : s.ncard = (s ∩ A).ncard + (s ∩ B).ncard := by conv_lhs => rw [hsdecomp] rw [Set.ncard_union_eq hsdisj] have hN_card : (⋃ x ∈ s, G.neighborSet x).ncard = (⋃ x ∈ s ∩ A, G.neighborSet x).ncard + (⋃ x ∈ s ∩ B, G.neighborSet x).ncard := by rw [hdecomp, Set.ncard_union_eq hNdisj] omega
SimpleGraph.exists_isPerfectMatching_of_forall_ncard_le- In a locally finite bipartite graph with parts A and B, if every vertex subset s satisfies |s| ≤ |N(s)|, then G admits a perfect matching.
bipartite_well_covered_has_perfect_matching_hall_side- For a well-covered bipartite graph with equal-size maximal independent sides A and B, any subset of A has its neighborhood in B of at least equal cardinality.
SimpleGraph.isMaximalIndepSet_iff- A vertex set is a maximal independent set if and only if it is independent and any independent superset is equal to it.
SimpleGraph.mem_neighborSet- A vertex w is in the neighbor set of v if and only if v and w are adjacent.
Set.mem_iUnion- An element belongs to a union of sets indexed by a family iff it belongs to at least one set in the family.
Set.disjoint_left- Two sets are disjoint if and only if no element of the first belongs to the second.
Set.disjoint_left.mp- If two sets are disjoint, an element of the first set cannot belong to the second set.
Set.toFinite- Every subset of a finite type is finite.
subset_refl- Any set is a subset of itself.
Set.Subset.trans- Set inclusion is transitive: if a ⊆ b and b ⊆ c, then a ⊆ c.
Set.ncard_le_ncard- If s ⊆ t and t is finite, then the cardinality of s is at most that of t.
Set.ncard_sdiff- If s ⊆ t and s is finite, then |t \ s| = |t| - |s|.
Set.ncard_union_eq- If s and t are disjoint finite sets, then |s ∪ t| = |s| + |t|.
Or.inl- Proof of a disjunction P ∨ Q from a proof of the left disjunct P.
Or.inr- Proof of a disjunction P ∨ Q from a proof of the right disjunct Q.
Set.univ- The set containing every element of the underlying type.
iff_true- A proposition p is equivalent to True if and only if p holds.
Fintype.card_le_one_iff.mpr- If any two elements of a type are equal, its cardinality as a finite type is at most 1.
Set.union_comm- Set union is commutative: a ∪ b = b ∪ a.
Set.Finite.coe_toFinset- Coercing the finset of a finite set back to a set yields the original set.
Set.Finite.mem_toFinset- An element belongs to the finset of a finite set iff it belongs to the set.
Set.ncard_eq_toFinset_card- The cardinality of a finite set equals the cardinality of its corresponding finset.
Set.inter_union_distrib_left- Intersection distributes over union: s ∩ (t ∪ u) = (s ∩ t) ∪ (s ∩ u).
Set.inter_univ- The intersection of any set with the universal set is the set itself.
Set.inter_subset_right- The intersection s ∩ t is a subset of t.
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 SimpleGraph in/-- Hall's condition for one side of a well-covered bipartite graph: for `t` contained in amaximum-cardinality independent side `A`, the neighbourhood of `t` is at least as large. -/private lemma bipartite_well_covered_has_perfect_matching_hall_side {V : Type*} [Fintype V] {G : SimpleGraph V} {A B : Set V} (hAB : G.IsBipartiteWith A B) (hAind : G.IsIndepSet A) (hBind : G.IsIndepSet B) (hAmax : ∀ s : Set V, Maximal G.IsIndepSet s → s.ncard = A.ncard) (hcardAB : A.ncard = B.ncard) (t : Set V) (ht : t ⊆ A) : t.ncard ≤ (⋃ x ∈ t, G.neighborSet x).ncard := by classical set N : Set V := ⋃ x ∈ t, G.neighborSet x with hNdef have hNsub : N ⊆ B := by intro y hy simp only [hNdef, Set.mem_iUnion, exists_prop] at hy obtain ⟨x, hxt, hyx⟩ := hy rw [SimpleGraph.mem_neighborSet] at hyx rcases hAB.mem_of_adj hyx with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact h2 · exact absurd h1 (Set.disjoint_left.mp hAB.disjoint (ht hxt)) have hIind : G.IsIndepSet (t ∪ (B \ N)) := by intro a ha b hb hab hadj rcases ha with ha | ⟨haB, haN⟩ · rcases hb with hb | ⟨hbB, hbN⟩ · exact hAind (ht ha) (ht hb) hab hadj · refine hbN ?_ simp only [hNdef, Set.mem_iUnion, exists_prop] exact ⟨a, ha, by rwa [SimpleGraph.mem_neighborSet]⟩ · rcases hb with hb | ⟨hbB, hbN⟩ · refine haN ?_ simp only [hNdef, Set.mem_iUnion, exists_prop] exact ⟨b, hb, by rw [SimpleGraph.mem_neighborSet]; exact hadj.symm⟩ · exact hBind haB hbB hab hadj have hSfin : {u : Set V | (t ∪ (B \ N)) ⊆ u ∧ G.IsIndepSet u}.Finite := Set.toFinite _ obtain ⟨J, hJ⟩ := hSfin.exists_maximal ⟨t ∪ (B \ N), subset_refl _, hIind⟩ have hJmax : Maximal G.IsIndepSet J := by refine ⟨hJ.1.2, ?_⟩ intro u hu hJu exact hJ.2 ⟨Set.Subset.trans hJ.1.1 hJu, hu⟩ hJu have hJcard : J.ncard = A.ncard := hAmax J hJmax have hIle : (t ∪ (B \ N)).ncard ≤ J.ncard := Set.ncard_le_ncard hJ.1.1 have hdisj : Disjoint t (B \ N) := by rw [Set.disjoint_left] intro x hx hx' exact Set.disjoint_left.mp hAB.disjoint (ht hx) hx'.1 have hNleB : N.ncard ≤ B.ncard := Set.ncard_le_ncard hNsub have hBN : (B \ N).ncard = B.ncard - N.ncard := Set.ncard_sdiff hNsub have hIunion : (t ∪ (B \ N)).ncard = t.ncard + (B \ N).ncard := Set.ncard_union_eq hdisj omega/-- Every finite connected well-covered bipartite graph with at least 2 vertices has a perfect matching. -/theorem bipartite_well_covered_has_perfect_matching {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (hbip : G.IsBipartite) (hcard : 2 ≤ Fintype.card V) (hwc : simple_graph_is_well_covered G) : ∃ M : SimpleGraph.Subgraph G, M.IsPerfectMatching := by classical haveI : G.LocallyFinite := fun v => (Set.toFinite _).fintype obtain ⟨C⟩ := hbip have htwo : ∀ x : Fin 2, x = 0 ∨ x = 1 := fun x => by fin_cases x <;> simp set A : Set V := C.colorClass 0 with hAdef set B : Set V := C.colorClass 1 with hBdef have hAB : G.IsBipartiteWith A B := by refine ⟨?_, ?_⟩ · rw [Set.disjoint_left] intro x hx hx' exact absurd (hx.symm.trans hx') (by decide) · intro v w hvw have hne := C.valid hvw have hv := htwo (C v) have hw := htwo (C w) rcases hv with h | h · refine Or.inl ⟨h, ?_⟩ rcases hw with h' | h' · exact absurd (h.trans h'.symm) hne · exact h' · refine Or.inr ⟨h, ?_⟩ rcases hw with h' | h' · exact h' · exact absurd (h.trans h'.symm) hne have hAind : G.IsIndepSet A := C.isIndepSet_colorClass 0 have hBind : G.IsIndepSet B := C.isIndepSet_colorClass 1 have hunion : A ∪ B = Set.univ := by ext v simp only [Set.mem_union, Set.mem_univ, iff_true] exact htwo (C v) have hne : ∀ v : V, ∃ w, G.Adj v w := by intro v obtain ⟨w, hw⟩ : ∃ w, w ≠ v := by by_contra h push Not at h have : Fintype.card V ≤ 1 := Fintype.card_le_one_iff.mpr fun a b => by rw [h a, h b] omega have hr : G.Reachable v w := hconn.preconnected v w exact hr.elim fun p => by cases p with | nil => exact absurd rfl hw | cons h _ => exact ⟨_, h⟩ have maxim : ∀ (P Q : Set V), G.IsBipartiteWith P Q → G.IsIndepSet P → P ∪ Q = Set.univ → Maximal G.IsIndepSet P := by intro P Q hPQ hPind hPQun rw [SimpleGraph.isMaximalIndepSet_iff] refine ⟨hPind, ?_⟩ intro u hu hPu x hx by_contra hxP have hxQ : x ∈ Q := by have h : x ∈ P ∪ Q := by rw [hPQun]; trivial exact h.resolve_left hxP obtain ⟨w, hxw⟩ := hne x have hwP : w ∈ P := by rcases hPQ.mem_of_adj hxw with ⟨h1, -⟩ | ⟨-, h2⟩ · exact absurd h1 hxP · exact h2 exact hu hx (hPu hwP) hxw.ne hxw have hAmaxS : Maximal G.IsIndepSet A := maxim A B hAB hAind hunion have hBmaxS : Maximal G.IsIndepSet B := by refine maxim B A hAB.symm hBind ?_ rw [Set.union_comm]; exact hunion have hwcS : ∀ s t : Set V, Maximal G.IsIndepSet s → Maximal G.IsIndepSet t → s.ncard = t.ncard := by intro s t hs ht have hsfin : s.Finite := Set.toFinite s have htfin : t.Finite := Set.toFinite t have key : ∀ (u : Set V), (hufin : u.Finite) → Maximal G.IsIndepSet u → Maximal (fun v : Finset V => G.IsIndepSet (↑v : Set V)) hufin.toFinset := by intro u hufin hu have hcoe : (↑hufin.toFinset : Set V) = u := Set.Finite.coe_toFinset hufin refine ⟨?_, ?_⟩ · show G.IsIndepSet (↑hufin.toFinset : Set V) rw [hcoe]; exact hu.1 · intro w hw huw have h1 : u ⊆ (↑w : Set V) := by rw [← hcoe]; exact huw have h2 : (↑w : Set V) ⊆ u := hu.2 hw h1 intro y hy rw [Set.Finite.mem_toFinset] exact h2 hy have h1 := key s hsfin hs have h2 := key t htfin ht have h := hwc hsfin.toFinset htfin.toFinset h1 h2 rw [Set.ncard_eq_toFinset_card s hsfin, Set.ncard_eq_toFinset_card t htfin] exact h have hcardAB : A.ncard = B.ncard := hwcS A B hAmaxS hBmaxS have hAmax : ∀ s : Set V, Maximal G.IsIndepSet s → s.ncard = A.ncard := fun s hs => hwcS s A hs hAmaxS have hBmax : ∀ s : Set V, Maximal G.IsIndepSet s → s.ncard = B.ncard := fun s hs => hwcS s B hs hBmaxS refine SimpleGraph.exists_isPerfectMatching_of_forall_ncard_le hAB ?_ intro s have hdecomp : (⋃ x ∈ s, G.neighborSet x) = (⋃ x ∈ s ∩ A, G.neighborSet x) ∪ (⋃ x ∈ s ∩ B, G.neighborSet x) := by ext y simp only [Set.mem_iUnion, Set.mem_inter_iff, Set.mem_union, exists_prop] constructor · rintro ⟨x, hx, hy⟩ rcases htwo (C x) with h | h · exact Or.inl ⟨x, ⟨hx, h⟩, hy⟩ · exact Or.inr ⟨x, ⟨hx, h⟩, hy⟩ · rintro (⟨x, ⟨hx, -⟩, hy⟩ | ⟨x, ⟨hx, -⟩, hy⟩) · exact ⟨x, hx, hy⟩ · exact ⟨x, hx, hy⟩ have hNdisj : Disjoint (⋃ x ∈ s ∩ A, G.neighborSet x) (⋃ x ∈ s ∩ B, G.neighborSet x) := by rw [Set.disjoint_left] intro y hy hy' simp only [Set.mem_iUnion, Set.mem_inter_iff, exists_prop] at hy hy' obtain ⟨x, ⟨-, hx0⟩, hyx⟩ := hy obtain ⟨x', ⟨-, hx1⟩, hyx'⟩ := hy' rw [SimpleGraph.mem_neighborSet] at hyx hyx' have hy1 : y ∈ B := by rcases hAB.mem_of_adj hyx with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact h2 · exact absurd h1 (Set.disjoint_left.mp hAB.disjoint hx0) have hy0 : y ∈ A := by rcases hAB.mem_of_adj hyx' with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 (Set.disjoint_right.mp hAB.disjoint hx1) · exact h2 exact Set.disjoint_left.mp hAB.disjoint hy0 hy1 have hsdecomp : s = (s ∩ A) ∪ (s ∩ B) := by rw [← Set.inter_union_distrib_left, hunion, Set.inter_univ] have hsdisj : Disjoint (s ∩ A) (s ∩ B) := by rw [Set.disjoint_left] intro x hx hx' exact Set.disjoint_left.mp hAB.disjoint hx.2 hx'.2 have h1 : (s ∩ A).ncard ≤ (⋃ x ∈ s ∩ A, G.neighborSet x).ncard := bipartite_well_covered_has_perfect_matching_hall_side hAB hAind hBind hAmax hcardAB _ Set.inter_subset_right have h2 : (s ∩ B).ncard ≤ (⋃ x ∈ s ∩ B, G.neighborSet x).ncard := bipartite_well_covered_has_perfect_matching_hall_side hAB.symm hBind hAind hBmax hcardAB.symm _ Set.inter_subset_right have hs_card : s.ncard = (s ∩ A).ncard + (s ∩ B).ncard := by conv_lhs => rw [hsdecomp] rw [Set.ncard_union_eq hsdisj] have hN_card : (⋃ x ∈ s, G.neighborSet x).ncard = (⋃ x ∈ s ∩ A, G.neighborSet x).ncard + (⋃ x ∈ s ∩ B, G.neighborSet x).ncard := by rw [hdecomp, Set.ncard_union_eq hNdisj] omega