AFTD Auto-Formalizing Theoretical Domains

bipartite_well_covered_perfect_matching_ravindra

theoremverified

In any finite connected well-covered bipartite graph G with at least 2 vertices, for any perfect matching M and any edge uv of M, every neighbor of u is adjacent to every neighbor of v.

Statement

theorem bipartite_well_covered_perfect_matching_ravindra {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) (hM : M.IsPerfectMatching)
    (u v : V) (huv : M.Adj u v) (x y : V) (hx : G.Adj u x) (hy : G.Adj v y) :
    G.Adj x y
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 contradiction: assuming neighbors x of u and y of v are non-adjacent, {x, y} is an independent set and extends to a maximal independent set s. In a connected well-covered bipartite graph, the two color classes are maximal independent sets of equal size |V|/2, so well-coveredness implies |s| = |V|/2. The matching involution f maps s to an image f(s) of the same size that is disjoint from s, and neither u nor v can belong to s or f(s). This exhibits a subset s ∪ f(s) ∪ {u, v} of V of size 2|s| + 2 = |V| + 2, contradicting that the graph has only |V| vertices.

  1. Assume for contradiction that x and y are not adjacent in G.

    The proof proceeds by contradiction: we assume `¬G.Adj x y` and aim to derive False.

    lines 8–9

      classical
      by_contra hxy
  2. Every vertex in G has at least one neighbor.

    Since |V| ≥ 2, for any vertex z there exists a distinct vertex w ≠ z, because otherwise all vertices would equal z and |V| ≤ 1. By connectedness, there is a walk from z to w; since w ≠ z, this walk cannot be trivial, so its first edge gives a neighbor of z.

    lines 10–21

    uses Fintype.card_le_one_iff.mpr

      have hne : ∀ z : V, ∃ w, G.Adj z w := by
        intro z
        obtain ⟨w, hw⟩ : ∃ w, w ≠ z := 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 z w := hconn.preconnected z w
        exact hr.elim fun p => by
          cases p with
          | nil => exact absurd rfl hw
          | cons h _ => exact ⟨_, h⟩
  3. The graph partitions into two independent sets A and B whose union is the entire vertex set V.

    Because G is bipartite, it admits a proper 2-coloring C. The color classes A = C⁻¹(0) and B = C⁻¹(1) are independent sets by definition, and every vertex belongs to A or B because every color in Fin 2 is either 0 or 1.

    lines 22–34

    uses Set.mem_union, Set.mem_univ, iff_true, Or.inl, Or.inr

      obtain ⟨C⟩ := hbip
      have htwo : ∀ c : Fin 2, c = 0 ∨ c = 1 := fun c => by fin_cases c <;> simp
      set A : Set V := C.colorClass 0 with hAdef
      set B : Set V := C.colorClass 1 with hBdef
      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 z
        simp only [Set.mem_union, Set.mem_univ, iff_true]
        rcases htwo (C z) with h | h
        · exact Or.inl h
        · exact Or.inr h
      have hmem : ∀ z : V, z ∈ A ∪ B := fun z => by rw [hunion]; trivial
  4. The color classes A and B are maximal independent sets.

    To show A is maximal, suppose an independent set t contains A. If there were a vertex z ∈ t \ A, then z must belong to B. Since every vertex has a neighbor, z is adjacent to some w. But B is independent, so w ∉ B, which means w ∈ A ⊆ t. This makes z, w ∈ t adjacent, contradicting the independence of t. By symmetry, B is also maximal.

    lines 35–64

    uses Set.mem_union

      have hAmax : Maximal G.IsIndepSet A := by
        refine ⟨hAind, ?_⟩
        intro t ht hAt z hz
        by_contra hzA
        have hzB : z ∈ B := by
          have h := hmem z
          rw [Set.mem_union] at h
          exact h.resolve_left hzA
        obtain ⟨w, hw⟩ := hne z
        have hwB : w ∉ B := fun hwB' => hBind hzB hwB' hw.ne hw
        have hwA : w ∈ A := by
          have h := hmem w
          rw [Set.mem_union] at h
          exact h.resolve_right hwB
        exact ht (hAt hwA) hz hw.ne.symm hw.symm
      have hBmax : Maximal G.IsIndepSet B := by
        refine ⟨hBind, ?_⟩
        intro t ht hBt z hz
        by_contra hzB
        have hzA : z ∈ A := by
          have h := hmem z
          rw [Set.mem_union] at h
          exact h.resolve_right hzB
        obtain ⟨w, hw⟩ := hne z
        have hwA : w ∉ A := fun hwA' => hAind hzA hwA' hw.ne hw
        have hwB : w ∈ B := by
          have h := hmem w
          rw [Set.mem_union] at h
          exact h.resolve_left hwA
        exact ht (hBt hwB) hz hw.ne.symm hw.symm
  5. The color classes AF and BF, as finite sets, are maximal independent finsets with |V| = |AF| + |BF|.

    Converting A and B into finsets AF and BF preserves their maximality among independent finsets. Since AF and BF are disjoint and their union is the entire vertex set, |V| = |AF| + |BF|.

    lines 65–109

    uses SimpleGraph.Coloring.colorClass, Finset.coe_subset.mpr, Finset.mem_coe.mp, Finset.disjoint_left, Finset.mem_filter, Finset.mem_univ, true_and, Finset.eq_univ_iff_forall.mpr, Finset.mem_union, Finset.card_union_of_disjoint, Finset.card_univ

      let AF : Finset V := Finset.univ.filter (fun z => C z = 0)
      let BF : Finset V := Finset.univ.filter (fun z => C z = 1)
      have hAFcoe : (AF : Set V) = A := by
        ext z; simp [AF, A, SimpleGraph.Coloring.colorClass]
      have hBFcoe : (BF : Set V) = B := by
        ext z; simp [BF, B, SimpleGraph.Coloring.colorClass]
      have hAFmax : Maximal (fun s : Finset V => G.IsIndepSet (s : Set V)) AF := by
        refine ⟨?_, ?_⟩
        · show G.IsIndepSet (AF : Set V)
          rw [hAFcoe]; exact hAind
        · intro t ht hsub
          have h1 : A ⊆ (t : Set V) := by
            rw [← hAFcoe]
            exact Finset.coe_subset.mpr hsub
          have h2 : (t : Set V) ⊆ A := hAmax.2 ht h1
          intro z hz
          exact Finset.mem_coe.mp (hAFcoe ▸ h2 hz)
      have hBFmax : Maximal (fun s : Finset V => G.IsIndepSet (s : Set V)) BF := by
        refine ⟨?_, ?_⟩
        · show G.IsIndepSet (BF : Set V)
          rw [hBFcoe]; exact hBind
        · intro t ht hsub
          have h1 : B ⊆ (t : Set V) := by
            rw [← hBFcoe]
            exact Finset.coe_subset.mpr hsub
          have h2 : (t : Set V) ⊆ B := hBmax.2 ht h1
          intro z hz
          exact Finset.mem_coe.mp (hBFcoe ▸ h2 hz)
      have hAFBFdisj : Disjoint AF BF := by
        rw [Finset.disjoint_left]
        intro z hz hz'
        simp only [AF, BF, Finset.mem_filter, Finset.mem_univ, true_and] at hz hz'
        exact absurd (hz.symm.trans hz') (by decide)
      have hAFBFun : AF ∪ BF = Finset.univ := by
        refine Finset.eq_univ_iff_forall.mpr ?_
        intro z
        rw [Finset.mem_union]
        simp only [AF, BF, Finset.mem_filter, Finset.mem_univ, true_and]
        rcases htwo (C z) with h | h
        · exact Or.inl h
        · exact Or.inr h
      have hVcard : Fintype.card V = AF.card + BF.card := by
        have h := Finset.card_union_of_disjoint hAFBFdisj
        rw [hAFBFun, Finset.card_univ] at h
        exact h
  6. The pair {x, y} extends to a maximal independent finset s with |s| = |AF| = |BF|.

    Because x and y are not adjacent, {x, y} is an independent set. The finite family of independent sets containing x and y is nonempty, so it contains a maximal element s under inclusion. Any independent set containing s must also contain x and y, so s is maximal among all independent finsets of G. Since G is well-covered, all maximal independent finsets have the same size, which implies |s| = |AF| = |BF|.

    lines 110–137

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.exists_maximal

      have hxyind : G.IsIndepSet ({x, y} : Set V) := by
        intro a ha b hb hab
        simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at ha hb
        rcases ha with rfl | rfl <;> rcases hb with rfl | rfl
        · exact absurd rfl hab
        · exact hxy
        · exact fun h => hxy h.symm
        · exact absurd rfl hab
      let fam : Finset (Finset V) :=
        Finset.univ.filter (fun t : Finset V => x ∈ t ∧ y ∈ t ∧ G.IsIndepSet (t : Set V))
      have hfamne : fam.Nonempty := by
        refine ⟨{x, y}, ?_⟩
        simp only [fam, Finset.mem_filter, Finset.mem_univ, true_and]
        exact ⟨by simp, by simp, by simpa using hxyind⟩
      obtain ⟨s, hsmax⟩ := Finset.exists_maximal hfamne
      have hsmem : x ∈ s ∧ y ∈ s ∧ G.IsIndepSet (s : Set V) := by
        have h := hsmax.1
        simp only [fam, Finset.mem_filter, Finset.mem_univ, true_and] at h
        exact h
      have hsFmax : Maximal (fun t : Finset V => G.IsIndepSet (t : Set V)) s := by
        refine ⟨hsmem.2.2, ?_⟩
        intro t ht hst
        have ht_fam : t ∈ fam := by
          refine Finset.mem_filter.mpr ⟨Finset.mem_univ t, ?_⟩
          exact ⟨hst hsmem.1, hst hsmem.2.1, ht⟩
        exact hsmax.2 ht_fam hst
      have hsA : s.card = AF.card := hwc s AF hsFmax hAFmax
      have hAB : AF.card = BF.card := hwc AF BF hAFmax hBFmax
  7. Neither u nor v belongs to s.

    The vertex u cannot belong to s because x ∈ s and u is adjacent to x (s is independent). Symmetrically, v cannot belong to s because y ∈ s and v is adjacent to y.

    lines 138–144

      have hu_not : u ∉ s := by
        intro hu
        exact hsmem.2.2 hu hsmem.1 hx.ne hx
      have hv_not : v ∉ s := by
        intro hv
        exact hsmem.2.2 hv hsmem.2.1 hy.ne hy
      have hspan : ∀ z : V, z ∈ M.verts := hM.2
  8. The perfect matching M defines a fixed-point-free involution f matching each vertex to its unique partner, with f(u) = v and f(v) = u.

    Each vertex z in a perfect matching is incident to a unique matching edge, defining a bijection f(z). Because matching edges are undirected edges of G, f is a fixed-point-free involution (f(f(z)) = z and f(z) ≠ z) whose edges belong to G. The edge uv of M implies f(u) = v and f(v) = u.

    lines 145–164

      have hmatch : ∀ z : V, ∃! w, M.Adj z w := fun z => hM.1 (hspan z)
      let f : V → V := fun z => (hmatch z).choose
      have hfadj : ∀ z, M.Adj z (f z) := fun z => (hmatch z).choose_spec.1
      have hfuniq : ∀ z w, M.Adj z w → w = f z := fun z w h => (hmatch z).choose_spec.2 w h
      have hfsym : ∀ z, f (f z) = z := by
        intro z
        exact (hfuniq (f z) z (M.symm.symm z (f z) (hfadj z))).symm
      have hfinj : Function.Injective f := by
        intro a b hab
        calc a = f (f a) := (hfsym a).symm
          _ = f (f b) := by rw [hab]
          _ = b := hfsym b
      have hfne : ∀ z, f z ≠ z := by
        intro z h
        have h1 : M.Adj z (f z) := hfadj z
        rw [h] at h1
        exact G.irrefl (M.adj_sub h1)
      have hfG : ∀ z, G.Adj z (f z) := fun z => M.adj_sub (hfadj z)
      have hfu : f u = v := (hfuniq u v huv).symm
      have hfv : f v = u := (hfuniq v u (M.symm.symm u v huv)).symm
  9. The matched image f(s) is disjoint from s, and |s ∪ f(s)| = 2|s|.

    If a vertex a belonged to s ∩ f(s), then a = f(b) for some b ∈ s, so a and b would be adjacent vertices in s, violating independence. Since f is injective, |f(s)| = |s|, so the disjoint union has cardinality |s| + |s| = 2|s|.

    lines 165–176

    uses Finset.disjoint_left, Finset.card_image_of_injective, Finset.card_union_of_disjoint

      have hdisj_img : Disjoint s (s.image f) := by
        rw [Finset.disjoint_left]
        intro a ha ha'
        obtain ⟨b, hb, hba⟩ := Finset.mem_image.mp ha'
        have hne' : b ≠ a := by
          rintro rfl
          exact hfne b hba
        have hAdj : G.Adj b a := by rw [← hba]; exact hfG b
        exact (hsmem.2.2 hb ha hne') hAdj
      have hcard_img : (s.image f).card = s.card := Finset.card_image_of_injective s hfinj
      have hcard_union : (s ∪ s.image f).card = s.card + s.card := by
        rw [Finset.card_union_of_disjoint hdisj_img, hcard_img]
  10. The pair {u, v} is disjoint from s ∪ f(s).

    We know u, v ∉ s. If u were in f(s), say u = f(a) for a ∈ s, then applying the involution gives a = f(u) = v, forcing v ∈ s, a contradiction. Similarly, v ∈ f(s) would imply u ∈ s. Therefore, {u, v} is disjoint from both s and f(s).

    lines 177–202

    uses congrArg, Finset.disjoint_left, Finset.mem_union

      have hu_not_img : u ∉ s.image f := by
        intro hu_img
        obtain ⟨a, ha, hfa⟩ := Finset.mem_image.mp hu_img
        have hav : a = v := by
          have h1 : f (f a) = f u := congrArg f hfa
          rw [hfsym a, hfu] at h1
          exact h1
        exact hv_not (hav ▸ ha)
      have hv_not_img : v ∉ s.image f := by
        intro hv_img
        obtain ⟨a, ha, hfa⟩ := Finset.mem_image.mp hv_img
        have hau : a = u := by
          have h1 : f (f a) = f v := congrArg f hfa
          rw [hfsym a, hfv] at h1
          exact h1
        exact hu_not (hau ▸ ha)
      have hdisj_uv : Disjoint (s ∪ s.image f) ({u, v} : Finset V) := by
        rw [Finset.disjoint_left]
        intro a ha ha'
        simp only [Finset.mem_union] at ha
        simp only [Finset.mem_insert, Finset.mem_singleton] at ha'
        rcases ha with ha | ha <;> rcases ha' with rfl | rfl
        · exact hu_not ha
        · exact hv_not ha
        · exact hu_not_img ha
        · exact hv_not_img ha
  11. Counting vertices gives 2|s| + 2 ≤ 2|s|, a contradiction.

    The union (s ∪ f(s)) ∪ {u, v} is formed by disjoint sets of sizes 2|s| and 2, so it has cardinality 2|s| + 2, and being a subset of V gives 2|s| + 2 ≤ |V|. However, |V| = |AF| + |BF| = 2|s|, yielding 2|s| + 2 ≤ 2|s|, which is impossible. Linear arithmetic (`omega`) closes the contradiction, completing the proof that x and y must be adjacent.

    lines 203–213

    uses Finset.card_union_of_disjoint, Finset.subset_univ, Finset.card_pair, Finset.card_univ, Finset.card_le_card

      have hupper : s.card + s.card + 2 ≤ Fintype.card V := by
        have h1 : ((s ∪ s.image f) ∪ ({u, v} : Finset V)).card
            = (s ∪ s.image f).card + ({u, v} : Finset V).card :=
          Finset.card_union_of_disjoint hdisj_uv
        have h2 : ((s ∪ s.image f) ∪ ({u, v} : Finset V)) ⊆ Finset.univ := Finset.subset_univ _
        have h3 : ({u, v} : Finset V).card = 2 := Finset.card_pair (M.adj_sub huv).ne
        have h4 : ((s ∪ s.image f) ∪ ({u, v} : Finset V)).card ≤ Fintype.card V := by
          rw [← Finset.card_univ]
          exact Finset.card_le_card h2
        omega
      omega
Fintype.card_le_one_iff.mpr
If all elements of a type are equal, then the cardinality of the type is at most 1.
Set.mem_union
An element belongs to the union of two sets if and only if it belongs to either set.
Set.mem_univ
Every element of a type belongs to its universal set.
iff_true
The proposition `p ↔ True` is equivalent to `p`.
Or.inl
From a proof of `a`, conclude `a ∨ b`.
Or.inr
From a proof of `b`, conclude `a ∨ b`.
SimpleGraph.Coloring.colorClass
The set of vertices assigned a given color by a graph coloring.
Finset.coe_subset.mpr
If a finset is a subset of another, their underlying sets satisfy the same subset relation.
Finset.mem_coe.mp
An element belongs to a finset coerced to a set if and only if it belongs to the finset.
Finset.disjoint_left
Two finsets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
true_and
The conjunction `True ∧ p` is logically equivalent to `p`.
Finset.eq_univ_iff_forall.mpr
A finset containing every element of a finite type is the universal finset.
Finset.mem_union
An element belongs to the union of two finsets if and only if it belongs to the first or the second.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.exists_maximal
Every nonempty finite family ordered by inclusion has a maximal element.
Finset.card_image_of_injective
An injective function preserves the cardinality of a finset under image.
congrArg
Applying a function to equal arguments yields equal results.
Finset.subset_univ
Every finset of a finite type is a subset of the universal finset.
Finset.card_pair
A set of two distinct elements has cardinality 2.
Finset.card_le_card
If one finset is a subset of another, its cardinality is at most the other's cardinality.

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

/-- Ravindra's neighborhood property: in a well-covered bipartite graph, any perfect matching has complete bipartite neighborhoods. -/theorem bipartite_well_covered_perfect_matching_ravindra {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) (hM : M.IsPerfectMatching)    (u v : V) (huv : M.Adj u v) (x y : V) (hx : G.Adj u x) (hy : G.Adj v y) :    G.Adj x y := by  classical  by_contra hxy  have hne : ∀ z : V, ∃ w, G.Adj z w := by    intro z    obtain ⟨w, hw⟩ : ∃ w, w ≠ z := 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 z w := hconn.preconnected z w    exact hr.elim fun p => by      cases p with      | nil => exact absurd rfl hw      | cons h _ => exact ⟨_, h⟩  obtain ⟨C⟩ := hbip  have htwo : ∀ c : Fin 2, c = 0 ∨ c = 1 := fun c => by fin_cases c <;> simp  set A : Set V := C.colorClass 0 with hAdef  set B : Set V := C.colorClass 1 with hBdef  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 z    simp only [Set.mem_union, Set.mem_univ, iff_true]    rcases htwo (C z) with h | h    · exact Or.inl h    · exact Or.inr h  have hmem : ∀ z : V, z ∈ A ∪ B := fun z => by rw [hunion]; trivial  have hAmax : Maximal G.IsIndepSet A := by    refine ⟨hAind, ?_⟩    intro t ht hAt z hz    by_contra hzA    have hzB : z ∈ B := by      have h := hmem z      rw [Set.mem_union] at h      exact h.resolve_left hzA    obtain ⟨w, hw⟩ := hne z    have hwB : w ∉ B := fun hwB' => hBind hzB hwB' hw.ne hw    have hwA : w ∈ A := by      have h := hmem w      rw [Set.mem_union] at h      exact h.resolve_right hwB    exact ht (hAt hwA) hz hw.ne.symm hw.symm  have hBmax : Maximal G.IsIndepSet B := by    refine ⟨hBind, ?_⟩    intro t ht hBt z hz    by_contra hzB    have hzA : z ∈ A := by      have h := hmem z      rw [Set.mem_union] at h      exact h.resolve_right hzB    obtain ⟨w, hw⟩ := hne z    have hwA : w ∉ A := fun hwA' => hAind hzA hwA' hw.ne hw    have hwB : w ∈ B := by      have h := hmem w      rw [Set.mem_union] at h      exact h.resolve_left hwA    exact ht (hBt hwB) hz hw.ne.symm hw.symm  let AF : Finset V := Finset.univ.filter (fun z => C z = 0)  let BF : Finset V := Finset.univ.filter (fun z => C z = 1)  have hAFcoe : (AF : Set V) = A := by    ext z; simp [AF, A, SimpleGraph.Coloring.colorClass]  have hBFcoe : (BF : Set V) = B := by    ext z; simp [BF, B, SimpleGraph.Coloring.colorClass]  have hAFmax : Maximal (fun s : Finset V => G.IsIndepSet (s : Set V)) AF := by    refine ⟨?_, ?_⟩    · show G.IsIndepSet (AF : Set V)      rw [hAFcoe]; exact hAind    · intro t ht hsub      have h1 : A ⊆ (t : Set V) := by        rw [← hAFcoe]        exact Finset.coe_subset.mpr hsub      have h2 : (t : Set V) ⊆ A := hAmax.2 ht h1      intro z hz      exact Finset.mem_coe.mp (hAFcoe ▸ h2 hz)  have hBFmax : Maximal (fun s : Finset V => G.IsIndepSet (s : Set V)) BF := by    refine ⟨?_, ?_⟩    · show G.IsIndepSet (BF : Set V)      rw [hBFcoe]; exact hBind    · intro t ht hsub      have h1 : B ⊆ (t : Set V) := by        rw [← hBFcoe]        exact Finset.coe_subset.mpr hsub      have h2 : (t : Set V) ⊆ B := hBmax.2 ht h1      intro z hz      exact Finset.mem_coe.mp (hBFcoe ▸ h2 hz)  have hAFBFdisj : Disjoint AF BF := by    rw [Finset.disjoint_left]    intro z hz hz'    simp only [AF, BF, Finset.mem_filter, Finset.mem_univ, true_and] at hz hz'    exact absurd (hz.symm.trans hz') (by decide)  have hAFBFun : AF ∪ BF = Finset.univ := by    refine Finset.eq_univ_iff_forall.mpr ?_    intro z    rw [Finset.mem_union]    simp only [AF, BF, Finset.mem_filter, Finset.mem_univ, true_and]    rcases htwo (C z) with h | h    · exact Or.inl h    · exact Or.inr h  have hVcard : Fintype.card V = AF.card + BF.card := by    have h := Finset.card_union_of_disjoint hAFBFdisj    rw [hAFBFun, Finset.card_univ] at h    exact h  have hxyind : G.IsIndepSet ({x, y} : Set V) := by    intro a ha b hb hab    simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at ha hb    rcases ha with rfl | rfl <;> rcases hb with rfl | rfl    · exact absurd rfl hab    · exact hxy    · exact fun h => hxy h.symm    · exact absurd rfl hab  let fam : Finset (Finset V) :=    Finset.univ.filter (fun t : Finset V => x ∈ t ∧ y ∈ t ∧ G.IsIndepSet (t : Set V))  have hfamne : fam.Nonempty := by    refine ⟨{x, y}, ?_⟩    simp only [fam, Finset.mem_filter, Finset.mem_univ, true_and]    exact ⟨by simp, by simp, by simpa using hxyind⟩  obtain ⟨s, hsmax⟩ := Finset.exists_maximal hfamne  have hsmem : x ∈ s ∧ y ∈ s ∧ G.IsIndepSet (s : Set V) := by    have h := hsmax.1    simp only [fam, Finset.mem_filter, Finset.mem_univ, true_and] at h    exact h  have hsFmax : Maximal (fun t : Finset V => G.IsIndepSet (t : Set V)) s := by    refine ⟨hsmem.2.2, ?_⟩    intro t ht hst    have ht_fam : t ∈ fam := by      refine Finset.mem_filter.mpr ⟨Finset.mem_univ t, ?_⟩      exact ⟨hst hsmem.1, hst hsmem.2.1, ht⟩    exact hsmax.2 ht_fam hst  have hsA : s.card = AF.card := hwc s AF hsFmax hAFmax  have hAB : AF.card = BF.card := hwc AF BF hAFmax hBFmax  have hu_not : u ∉ s := by    intro hu    exact hsmem.2.2 hu hsmem.1 hx.ne hx  have hv_not : v ∉ s := by    intro hv    exact hsmem.2.2 hv hsmem.2.1 hy.ne hy  have hspan : ∀ z : V, z ∈ M.verts := hM.2  have hmatch : ∀ z : V, ∃! w, M.Adj z w := fun z => hM.1 (hspan z)  let f : V → V := fun z => (hmatch z).choose  have hfadj : ∀ z, M.Adj z (f z) := fun z => (hmatch z).choose_spec.1  have hfuniq : ∀ z w, M.Adj z w → w = f z := fun z w h => (hmatch z).choose_spec.2 w h  have hfsym : ∀ z, f (f z) = z := by    intro z    exact (hfuniq (f z) z (M.symm.symm z (f z) (hfadj z))).symm  have hfinj : Function.Injective f := by    intro a b hab    calc a = f (f a) := (hfsym a).symm      _ = f (f b) := by rw [hab]      _ = b := hfsym b  have hfne : ∀ z, f z ≠ z := by    intro z h    have h1 : M.Adj z (f z) := hfadj z    rw [h] at h1    exact G.irrefl (M.adj_sub h1)  have hfG : ∀ z, G.Adj z (f z) := fun z => M.adj_sub (hfadj z)  have hfu : f u = v := (hfuniq u v huv).symm  have hfv : f v = u := (hfuniq v u (M.symm.symm u v huv)).symm  have hdisj_img : Disjoint s (s.image f) := by    rw [Finset.disjoint_left]    intro a ha ha'    obtain ⟨b, hb, hba⟩ := Finset.mem_image.mp ha'    have hne' : b ≠ a := by      rintro rfl      exact hfne b hba    have hAdj : G.Adj b a := by rw [← hba]; exact hfG b    exact (hsmem.2.2 hb ha hne') hAdj  have hcard_img : (s.image f).card = s.card := Finset.card_image_of_injective s hfinj  have hcard_union : (s ∪ s.image f).card = s.card + s.card := by    rw [Finset.card_union_of_disjoint hdisj_img, hcard_img]  have hu_not_img : u ∉ s.image f := by    intro hu_img    obtain ⟨a, ha, hfa⟩ := Finset.mem_image.mp hu_img    have hav : a = v := by      have h1 : f (f a) = f u := congrArg f hfa      rw [hfsym a, hfu] at h1      exact h1    exact hv_not (hav ▸ ha)  have hv_not_img : v ∉ s.image f := by    intro hv_img    obtain ⟨a, ha, hfa⟩ := Finset.mem_image.mp hv_img    have hau : a = u := by      have h1 : f (f a) = f v := congrArg f hfa      rw [hfsym a, hfv] at h1      exact h1    exact hu_not (hau ▸ ha)  have hdisj_uv : Disjoint (s ∪ s.image f) ({u, v} : Finset V) := by    rw [Finset.disjoint_left]    intro a ha ha'    simp only [Finset.mem_union] at ha    simp only [Finset.mem_insert, Finset.mem_singleton] at ha'    rcases ha with ha | ha <;> rcases ha' with rfl | rfl    · exact hu_not ha    · exact hv_not ha    · exact hu_not_img ha    · exact hv_not_img ha  have hupper : s.card + s.card + 2 ≤ Fintype.card V := by    have h1 : ((s ∪ s.image f) ∪ ({u, v} : Finset V)).card        = (s ∪ s.image f).card + ({u, v} : Finset V).card :=      Finset.card_union_of_disjoint hdisj_uv    have h2 : ((s ∪ s.image f) ∪ ({u, v} : Finset V)) ⊆ Finset.univ := Finset.subset_univ _    have h3 : ({u, v} : Finset V).card = 2 := Finset.card_pair (M.adj_sub huv).ne    have h4 : ((s ∪ s.image f) ∪ ({u, v} : Finset V)).card ≤ Fintype.card V := by      rw [← Finset.card_univ]      exact Finset.card_le_card h2    omega  omega
See it in the graphDiscuss this resultChallenge it