bipartite_well_covered_perfect_matching_ravindra
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
- 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 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.
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.
classical by_contra hxyEvery 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.
uses
Fintype.card_le_one_iff.mprhave 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⟩
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.
uses
Set.mem_union,Set.mem_univ,iff_true,Or.inl,Or.inrobtain ⟨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
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.
uses
Set.mem_unionhave 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
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|.
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_univlet 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
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|.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.exists_maximalhave 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
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.
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
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.
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
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|.
uses
Finset.disjoint_left,Finset.card_image_of_injective,Finset.card_union_of_disjointhave 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]
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).
uses
congrArg,Finset.disjoint_left,Finset.mem_unionhave 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
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.
uses
Finset.card_union_of_disjoint,Finset.subset_univ,Finset.card_pair,Finset.card_univ,Finset.card_le_cardhave 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.
- Because Lean distinguishes between sets (`Set V`) and finite sets (`Finset V`), the proof explicitly transfers the maximality of the color classes from `Set V` to `Finset V` in lines 65–92 before applying the definition of well-coveredness.
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.
/-- 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