AFTD Auto-Formalizing Theoretical Domains

bipartite_well_covered_has_perfect_matching

theoremverified

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
Used by 1

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)|.

  1. 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.

    lines 10–19

    uses Set.mem_iUnion, SimpleGraph.mem_neighborSet, Set.disjoint_left.mp

      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))
  2. 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.

    lines 20–32

    uses SimpleGraph.mem_neighborSet, Set.mem_iUnion

      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
  3. 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|.

    lines 33–39

    uses Set.toFinite, subset_refl, Set.Subset.trans

      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
  4. |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|.

    lines 40–48

    uses Set.ncard_le_ncard, Set.disjoint_left, Set.disjoint_left.mp, Set.ncard_sdiff, Set.ncard_union_eq

      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
  5. 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.

    lines 55–84

    uses Set.toFinite, Set.disjoint_left, Or.inl, Or.inr, Set.univ, iff_true

      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)
  6. 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.

    lines 85–96

    uses Fintype.card_le_one_iff.mpr

      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⟩
  7. 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.

    lines 97–116

    uses SimpleGraph.isMaximalIndepSet_iff, Set.union_comm

      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
  8. 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|.

    lines 117–144

    uses Set.toFinite, Set.Finite.coe_toFinset, Set.Finite.mem_toFinset, Set.ncard_eq_toFinset_card

      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
  9. 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.

    lines 145–175

    uses SimpleGraph.exists_isPerfectMatching_of_forall_ncard_le, Set.mem_iUnion, SimpleGraph.mem_neighborSet, Set.disjoint_left, Set.disjoint_left.mp

      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
  10. |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.

    lines 176–195

    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_eq

      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
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

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
See it in the graphDiscuss this resultChallenge it