konig_matching_vertex_cover_num
König's theorem: in any finite bipartite simple graph G, the matching number is equal to the vertex cover number.
Statement
theorem konig_matching_vertex_cover_num {V : Type*} [Fintype V] (G : SimpleGraph V) (h : G.IsBipartite) : graph_matching_num G = G.vertexCoverNum
- Formalizes
- Diestel, Graph Theory, Theorem 2.1.1
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- graph_matching_numThe matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.
- graph_matching_num_le_vertex_cover_numIn any simple graph G, the matching number is at most the vertex cover number.
- bipartite_hall_step_is_vertex_coverIn a bipartite graph with partition (A, B) and a vertex cover C, for any subset S of A ∩ C, the set (C \ S) ∪ (N(S) ∩ (B \ C)) is also a…
- isMatching_sup_disjoint_encardFor two matchings M and M' in G with disjoint vertex sets, their supremum M ⊔ M' is also a matching, and its edge cardinality is the sum…
Read back from the Lean
For any finite type $V$ and any simple graph $G$ on $V$, if $G$ is bipartite, then the matching number of $G$ (graph_matching_num G) equals the vertex cover number of $G$ (G.vertexCoverNum).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
König's theorem states that in any finite bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover. One inequality is universal; for the reverse, let C be a minimum vertex cover and partition the bipartite sides into A and B. Hall's Marriage Theorem ensures that A ∩ C can be injectively matched into B \ C (and symmetrically B ∩ C into A \ C), because any violation would yield a strictly smaller vertex cover. These two independent matchings are vertex-disjoint and combine into a single matching of size |A ∩ C| + |B ∩ C| = |C|, witnessing that the matching number is at least the vertex cover number.
Set up the finite domain X = A ∩ C and the target neighborhood function t(a) = {b ∈ B \ C | G.Adj a b} for each a ∈ X.
We restrict attention to the finite set of vertices X representing A ∩ C, and define t(a) as the set of neighbors of a in B that lie outside C. We also note that every element of A ∩ C belongs to X.
classical let X : Finset V := Finset.univ.filter fun v => v ∈ A ∩ C let t : X → Finset V := fun a => Finset.univ.filter fun b => b ∈ B ∧ b ∉ C ∧ G.Adj a b have hX : ∀ v, v ∈ A ∩ C → v ∈ X := fun v hv => by simpa [X] using hv
Under the assumption that Hall's condition fails for some s ⊆ X, (C \ s) ∪ N_B(s) is a vertex cover of G whose size is at least |C|.
We argue by contradiction, assuming |s.biUnion t| < |s| for some s. Mapping s to a subset Sf ⊆ A ∩ C, bipartite_hall_step_is_vertex_cover establishes that removing Sf from C and adding its B \ C neighbors produces a valid vertex cover. Minimality of C implies C.encard ≤ (vertex cover).encard.
uses
bipartite_hall_step_is_vertex_coverhave hmarr : ∀ s : Finset X, s.card ≤ (s.biUnion t).card := by intro s by_contra hlt push Not at hlt let Sf : Finset V := s.map (Function.Embedding.subtype _) have hS : (Sf : Set V) ⊆ A ∩ C := by intro v hv obtain ⟨x, -, rfl⟩ := Finset.mem_map.1 (Finset.mem_coe.1 hv) have := x.2 simpa [X] using this have hcov := bipartite_hall_step_is_vertex_cover G A B C Sf hdisj hadj hC hS have hle := hcov.vertexCoverNum_le rw [← hmin] at hle
The modified vertex cover is contained in the finset (Cf \ Sf) ∪ s.biUnion t.
Any vertex v in the modified vertex cover either belongs to C \ Sf (hence to Cf \ Sf) or is a neighbor in B \ C of some vertex in Sf (hence belongs to t(x) for some x ∈ s).
let Cf : Finset V := Finset.univ.filter fun v => v ∈ C have hCe : C.encard = (Cf.card : ℕ∞) := by have hCf : C = (Cf : Set V) := by ext v; simp [Cf] rw [hCf, Set.encard_coe_eq_coe_finsetCard] have hsub : (C \ (Sf : Set V)) ∪ {b ∈ B \ C | ∃ a ∈ (Sf : Set V), G.Adj a b} ⊆ (((Cf \ Sf) ∪ s.biUnion t : Finset V) : Set V) := by rintro v (⟨hvC, hvS⟩ | ⟨⟨hvB, hvC⟩, a, haS, hav⟩) · have : v ∈ Cf \ Sf := Finset.mem_sdiff.2 ⟨by simp [Cf, hvC], fun h => hvS (Finset.mem_coe.2 h)⟩ exact Finset.mem_coe.2 (Finset.mem_union_left _ this) · obtain ⟨x, hx, rfl⟩ := Finset.mem_map.1 (Finset.mem_coe.1 haS) refine Finset.mem_coe.2 (Finset.mem_union_right _ (Finset.mem_biUnion.2 ⟨x, hx, ?_⟩)) simp only [t, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hvB, hvC, hav⟩
Hall's condition s.card ≤ (s.biUnion t).card holds for all s : Finset X. automation
Combining the set inclusion with subadditivity of finset cardinality yields |Cf| ≤ |Cf \ Sf ∪ s.biUnion t| ≤ |Cf| - |s| + |s.biUnion t| < |Cf|, a contradiction resolved by integer arithmetic.
uses
Finset.card_union_le,Finset.card_sdiff_add_card_eq_card,Finset.card_map,le_transhave h1 := Set.encard_le_encard hsub rw [Set.encard_coe_eq_coe_finsetCard] at h1 have hSC : Sf ⊆ Cf := by intro v hv have := hS (Finset.mem_coe.2 hv) simp [Cf, this.2] have h2 := Finset.card_union_le (Cf \ Sf) (s.biUnion t) have h3 := Finset.card_sdiff_add_card_eq_card hSC have h4 : Sf.card = s.card := Finset.card_map _ have h5 := le_trans hle h1 rw [hCe] at h5 norm_cast at h5 omega
There exists an injection F on A ∩ C matching each vertex to a neighbor in B \ C.
Hall's Marriage Theorem (Finset.all_card_le_biUnion_card_iff_exists_injective) gives an injective map f on X into the target sets t. Extending f by the identity outside X gives a function F that is injective on A ∩ C and sends each a ∈ A ∩ C to an adjacent vertex in B \ C.
uses
Finset.all_card_le_biUnion_card_iff_exists_injective,dif_pos,congrArgobtain ⟨f, hfi, hft⟩ := (Finset.all_card_le_biUnion_card_iff_exists_injective t).1 hmarr refine ⟨fun v => if h : v ∈ X then f ⟨v, h⟩ else v, ?_, ?_⟩ · intro a ha b hb hab dsimp only at hab rw [dif_pos (hX a ha), dif_pos (hX b hb)] at hab exact congrArg Subtype.val (hfi hab) · intro a ha dsimp only rw [dif_pos (hX a ha)] have := hft ⟨a, hX a ha⟩ simpa [t] using this
The vertices P and F(P) are disjoint, and we define a subgraph M with edges between each a ∈ P and F(a).
Because P ⊆ D and F(P) is disjoint from D, no F(a) equals any b ∈ P. We define M on vertices P ∪ F '' P with symmetric edges between a and F(a) for all a ∈ P.
have hsep : ∀ a ∈ P, ∀ b ∈ P, F a ≠ b := fun a ha b hb h => hFD a ha (h ▸ hPD hb) let M : G.Subgraph := { verts := P ∪ F '' P Adj := fun v w => ∃ a ∈ P, (v = a ∧ w = F a) ∨ (v = F a ∧ w = a) adj_sub := by rintro v w ⟨a, ha, ⟨h1, h2⟩ | ⟨h1, h2⟩⟩ · rw [h1, h2]; exact hadjF a ha · rw [h1, h2]; exact (hadjF a ha).symm edge_vert := by rintro v w ⟨a, ha, ⟨h1, -⟩ | ⟨h1, -⟩⟩ · rw [h1]; exact Or.inl ha · rw [h1]; exact Or.inr ⟨a, ha, rfl⟩ symm := ⟨fun v w ⟨a, ha, h⟩ => ⟨a, ha, h.symm.imp (fun h => ⟨h.2, h.1⟩) (fun h => ⟨h.2, h.1⟩)⟩⟩ } have hMadj : ∀ v w, M.Adj v w ↔ ∃ a ∈ P, (v = a ∧ w = F a) ∨ (v = F a ∧ w = a) := fun v w => Iff.rfl
The subgraph M is a matching.
We show every vertex in M has a unique incident edge in M. For v ∈ P, its only incident edge connects to F(v) by disjointness of P and F(P); for F(a) ∈ F(P), its only neighbor is a by injectivity of F and disjointness.
uses
subset_rflrefine ⟨M, ?_, subset_rfl, ?_⟩ · rintro v (hv | ⟨a, ha, rfl⟩) · refine ⟨F v, (hMadj _ _).2 ⟨v, hv, Or.inl ⟨rfl, rfl⟩⟩, fun y hy => ?_⟩ obtain ⟨a, ha, h⟩ := (hMadj _ _).1 hy rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h2, h1] · exact absurd h1.symm (hsep a ha v hv) · refine ⟨a, (hMadj _ _).2 ⟨a, ha, Or.inr ⟨rfl, rfl⟩⟩, fun y hy => ?_⟩ obtain ⟨b, hb, h⟩ := (hMadj _ _).1 hy rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 (hsep a ha b hb) · exact h2.trans (hinj hb ha h1.symm)
The edge set of M has extended cardinality equal to P.encard.
Every edge of M is an unordered pair s(a, F(a)) for a uniquely determined a ∈ P. The assignment a ↦ s(a, F(a)) is injective because F(a) ∉ P, so the cardinality of M.edgeSet equals P.encard by Set.InjOn.encard_image.
uses
Sym2.ind,SimpleGraph.Subgraph.mem_edgeSet,Set.mem_image,Sym2.eq_swap,Set.InjOn.encard_image· have hE : M.edgeSet = (fun a => s(a, F a)) '' P := by ext e induction e using Sym2.ind with | h v w => rw [SimpleGraph.Subgraph.mem_edgeSet, hMadj, Set.mem_image] constructor · rintro ⟨a, ha, h⟩ refine ⟨a, ha, ?_⟩ rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · rfl · exact Sym2.eq_swap · rintro ⟨a, ha, he⟩ refine ⟨a, ha, ?_⟩ rcases Sym2.eq_iff.1 he with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact Or.inl ⟨h1.symm, h2.symm⟩ · exact Or.inr ⟨h2.symm, h1.symm⟩ rw [hE] refine Set.InjOn.encard_image fun a ha b hb hab => ?_ rcases Sym2.eq_iff.1 hab with ⟨h1, -⟩ | ⟨h1, -⟩ · exact h1 · exact absurd h1.symm (hsep b hb a ha)
König's theorem reduces to showing vertexCoverNum ≤ graph_matching_num G; we choose a 2-coloring c and a minimum vertex cover C.
By antisymmetry and the known inequality graph_matching_num G ≤ G.vertexCoverNum, it suffices to construct a matching of size at least |C|. We unpack the bipartite coloring c and the existence of a minimum vertex cover C.
uses
le_antisymm,graph_matching_num_le_vertex_cover_numclassical refine le_antisymm (graph_matching_num_le_vertex_cover_num G) ?_ obtain ⟨c⟩ := h obtain ⟨C, hCe, hC⟩ := G.vertexCoverNum_exists
The color classes A and B form a partition of V such that all edges go between A and B.
Vertices with color 0 define A and color 1 define B. They are disjoint and cover V because Fin 2 has only values 0 and 1. Any edge has endpoints of different colors, so it must connect A and B.
let A : Set V := {v | c v = 0} let B : Set V := {v | c v = 1} have h01 : ∀ x : Fin 2, x = 0 ∨ x = 1 := by decide have hdisj : Disjoint A B := by refine Set.disjoint_left.2 fun v ha hb => ?_ have h1 : c v = 0 := ha have h2 : c v = 1 := hb rw [h1] at h2 exact absurd h2 (by decide) have hAB : ∀ v, v ∈ A ∨ v ∈ B := fun v => h01 (c v) have hadj : ∀ ⦃v w⦄, G.Adj v w → (v ∈ A ∧ w ∈ B) ∨ (v ∈ B ∧ w ∈ A) := by intro v w hvw have hne := c.valid hvw rcases h01 (c v) with h1 | h1 <;> rcases h01 (c w) with h2 | h2 · exact absurd (h1.trans h2.symm) hne · exact Or.inl ⟨h1, h2⟩ · exact Or.inr ⟨h1, h2⟩ · exact absurd (h1.trans h2.symm) hne have hadj' : ∀ ⦃v w⦄, G.Adj v w → (v ∈ B ∧ w ∈ A) ∨ (v ∈ A ∧ w ∈ B) := fun v w h => (hadj h).symm
There exist matchings MA on (A ∩ C) ∪ FA(A ∩ C) and MB on (B ∩ C) ∪ FB(B ∩ C) of sizes |A ∩ C| and |B ∩ C|.
Applying bipartite_min_cover_side_inj_neighbors to side A gives an injection FA from A ∩ C into B \ C; by subgraph_matching_of_injOn_neighbors, this induces a matching MA of size |A ∩ C|. Symmetrically, we obtain FB from B ∩ C into A \ C and a matching MB of size |B ∩ C|.
uses
bipartite_min_cover_side_inj_neighbors,subgraph_matching_of_injOn_neighbors,Set.inter_subset_rightobtain ⟨FA, hFAi, hFA⟩ := bipartite_min_cover_side_inj_neighbors G A B C hdisj hadj hC hCe obtain ⟨FB, hFBi, hFB⟩ := bipartite_min_cover_side_inj_neighbors G B A C hdisj.symm hadj' hC hCe obtain ⟨MA, hMA, hvA, heA⟩ := subgraph_matching_of_injOn_neighbors G (A ∩ C) C FA hFAi (fun a ha => (hFA a ha).2.2) Set.inter_subset_right (fun a ha => (hFA a ha).2.1) obtain ⟨MB, hMB, hvB, heB⟩ := subgraph_matching_of_injOn_neighbors G (B ∩ C) C FB hFBi (fun a ha => (hFB a ha).2.2) Set.inter_subset_right (fun a ha => (hFB a ha).2.1)
The matchings MA and MB are vertex-disjoint, so their union MA ⊔ MB is a matching of size |MA| + |MB|.
The vertices of MA lie in A ∪ (B \ C) and those of MB lie in B ∪ (A \ C). Their intersections are empty because A and B are disjoint, and C is disjoint from its complements. By isMatching_sup_disjoint_encard, their union is a matching whose edge count is the sum of edge counts.
uses
isMatching_sup_disjoint_encardhave hd : Disjoint MA.verts MB.verts := by refine Set.disjoint_left.2 fun v hva hvb => ?_ rcases hvA hva with hv1 | ⟨a, ha, rfl⟩ <;> rcases hvB hvb with hv2 | ⟨b, hb, hv2⟩ · exact Set.disjoint_left.1 hdisj hv1.1 hv2.1 · exact (hFB b hb).2.1 (by rw [hv2]; exact hv1.2) · exact (hFA a ha).2.1 hv2.2 · exact Set.disjoint_left.1 hdisj (by rw [← hv2]; exact (hFB b hb).1) (hFA a ha).1 obtain ⟨hM, hcard⟩ := isMatching_sup_disjoint_encard MA MB hMA hMB hd
The matching number of G is at least the vertex cover number, completing the proof of König's theorem.
We partition C into the disjoint sets A ∩ C and B ∩ C. Then |C| = |A ∩ C| + |B ∩ C| = |MA ⊔ MB|, which is at most graph_matching_num G by definition of the matching number as the supremum over all matchings. Together with the reverse inequality, this proves equality.
uses
Set.inter_subset_left,Set.encard_union_eq,le_iSup₂have hCsplit : C = (A ∩ C) ∪ (B ∩ C) := by ext v constructor · intro hv rcases hAB v with h | h · exact Or.inl ⟨h, hv⟩ · exact Or.inr ⟨h, hv⟩ · rintro (⟨-, hv⟩ | ⟨-, hv⟩) <;> exact hv have hCdisj : Disjoint (A ∩ C) (B ∩ C) := hdisj.mono Set.inter_subset_left Set.inter_subset_left calc G.vertexCoverNum = C.encard := hCe.symm _ = (A ∩ C).encard + (B ∩ C).encard := by rw [← Set.encard_union_eq hCdisj, ← hCsplit] _ = (MA ⊔ MB).edgeSet.encard := by rw [hcard, heA, heB] _ ≤ graph_matching_num G := le_iSup₂ (f := fun (M : G.Subgraph) (_ : M.IsMatching) => M.edgeSet.encard) (MA ⊔ MB) hM
bipartite_hall_step_is_vertex_cover- In a bipartite graph with sides A and B, if C is a vertex cover and S ⊆ A ∩ C, replacing S with its B \ C neighbors yields another vertex cover.
Finset.card_union_le- The cardinality of a union of two finite sets is at most the sum of their cardinalities.
Finset.card_sdiff_add_card_eq_card- If s ⊆ t, then |t \ s| + |s| = |t| for finite sets.
Finset.card_map- The image of a finite set under an embedding has the same cardinality.
le_trans- If a ≤ b and b ≤ c, then a ≤ c in a preorder.
Finset.all_card_le_biUnion_card_iff_exists_injective- Hall's Marriage Theorem: |s| ≤ |⋃_{x ∈ s} t(x)| for all s if and only if there exists an injective choice function f with f(x) ∈ t(x).
dif_pos- Evaluating a dependent if-then-else on a true proposition yields the then-branch.
congrArg- Congruence of application: equal inputs yield equal outputs under any function.
subset_rfl- Every set is a subset of itself.
Sym2.ind- Induction principle for unordered pairs: any property holding for all s(x, y) holds for every element of Sym2 α.
SimpleGraph.Subgraph.mem_edgeSet- An unordered pair s(v, w) belongs to the edge set of a subgraph if and only if v and w are adjacent in the subgraph.
Set.mem_image- An element belongs to the image f '' s if and only if it is the image of some element of s.
Sym2.eq_swap- An unordered pair s(a, b) equals s(b, a).
Set.InjOn.encard_image- If f is injective on s, the extended cardinality of the image f '' s equals that of s.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
graph_matching_num_le_vertex_cover_num- The matching number of any graph is at most its vertex cover number.
bipartite_min_cover_side_inj_neighbors- In a finite bipartite graph, any minimum vertex cover C can be injectively matched from A ∩ C to neighbors in B \ C.
subgraph_matching_of_injOn_neighbors- An injective neighbor choice F on P ⊆ D with F(P) outside D induces a matching of size |P| on P ∪ F(P).
Set.inter_subset_right- The intersection of two sets is a subset of the second set.
Set.inter_subset_left- The intersection of two sets is a subset of the first set.
isMatching_sup_disjoint_encard- The union of two vertex-disjoint matchings is a matching whose size is the sum of their sizes.
Set.encard_union_eq- The extended cardinality of the union of two disjoint sets is the sum of their extended cardinalities.
le_iSup₂- Any value in a doubly indexed family is at most its double supremum.
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.
/-- In a bipartite graph with sides `A`, `B`, the part `A ∩ C` of a minimum vertex cover `C` can bematched injectively to neighbours in `B` outside `C` (the marriage condition holds by minimality). -/theorem bipartite_min_cover_side_inj_neighbors {V : Type*} [Fintype V] (G : SimpleGraph V) (A B C : Set V) (hdisj : Disjoint A B) (hadj : ∀ ⦃v w⦄, G.Adj v w → (v ∈ A ∧ w ∈ B) ∨ (v ∈ B ∧ w ∈ A)) (hC : G.IsVertexCover C) (hmin : C.encard = G.vertexCoverNum) : ∃ F : V → V, Set.InjOn F (A ∩ C) ∧ ∀ a ∈ A ∩ C, F a ∈ B ∧ F a ∉ C ∧ G.Adj a (F a) := by classical let X : Finset V := Finset.univ.filter fun v => v ∈ A ∩ C let t : X → Finset V := fun a => Finset.univ.filter fun b => b ∈ B ∧ b ∉ C ∧ G.Adj a b have hX : ∀ v, v ∈ A ∩ C → v ∈ X := fun v hv => by simpa [X] using hv have hmarr : ∀ s : Finset X, s.card ≤ (s.biUnion t).card := by intro s by_contra hlt push Not at hlt let Sf : Finset V := s.map (Function.Embedding.subtype _) have hS : (Sf : Set V) ⊆ A ∩ C := by intro v hv obtain ⟨x, -, rfl⟩ := Finset.mem_map.1 (Finset.mem_coe.1 hv) have := x.2 simpa [X] using this have hcov := bipartite_hall_step_is_vertex_cover G A B C Sf hdisj hadj hC hS have hle := hcov.vertexCoverNum_le rw [← hmin] at hle let Cf : Finset V := Finset.univ.filter fun v => v ∈ C have hCe : C.encard = (Cf.card : ℕ∞) := by have hCf : C = (Cf : Set V) := by ext v; simp [Cf] rw [hCf, Set.encard_coe_eq_coe_finsetCard] have hsub : (C \ (Sf : Set V)) ∪ {b ∈ B \ C | ∃ a ∈ (Sf : Set V), G.Adj a b} ⊆ (((Cf \ Sf) ∪ s.biUnion t : Finset V) : Set V) := by rintro v (⟨hvC, hvS⟩ | ⟨⟨hvB, hvC⟩, a, haS, hav⟩) · have : v ∈ Cf \ Sf := Finset.mem_sdiff.2 ⟨by simp [Cf, hvC], fun h => hvS (Finset.mem_coe.2 h)⟩ exact Finset.mem_coe.2 (Finset.mem_union_left _ this) · obtain ⟨x, hx, rfl⟩ := Finset.mem_map.1 (Finset.mem_coe.1 haS) refine Finset.mem_coe.2 (Finset.mem_union_right _ (Finset.mem_biUnion.2 ⟨x, hx, ?_⟩)) simp only [t, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hvB, hvC, hav⟩ have h1 := Set.encard_le_encard hsub rw [Set.encard_coe_eq_coe_finsetCard] at h1 have hSC : Sf ⊆ Cf := by intro v hv have := hS (Finset.mem_coe.2 hv) simp [Cf, this.2] have h2 := Finset.card_union_le (Cf \ Sf) (s.biUnion t) have h3 := Finset.card_sdiff_add_card_eq_card hSC have h4 : Sf.card = s.card := Finset.card_map _ have h5 := le_trans hle h1 rw [hCe] at h5 norm_cast at h5 omega obtain ⟨f, hfi, hft⟩ := (Finset.all_card_le_biUnion_card_iff_exists_injective t).1 hmarr refine ⟨fun v => if h : v ∈ X then f ⟨v, h⟩ else v, ?_, ?_⟩ · intro a ha b hb hab dsimp only at hab rw [dif_pos (hX a ha), dif_pos (hX b hb)] at hab exact congrArg Subtype.val (hfi hab) · intro a ha dsimp only rw [dif_pos (hX a ha)] have := hft ⟨a, hX a ha⟩ simpa [t] using this/-- An injective choice of neighbours `a ↦ F a` on a finite set `P`, with `P` inside a set `D` andevery `F a` outside it, gives a matching with `|P|` edges on the vertices `P ∪ F(P)`. -/theorem subgraph_matching_of_injOn_neighbors {V : Type*} (G : SimpleGraph V) (P D : Set V) (F : V → V) (hinj : Set.InjOn F P) (hadjF : ∀ a ∈ P, G.Adj a (F a)) (hPD : P ⊆ D) (hFD : ∀ a ∈ P, F a ∉ D) : ∃ M : G.Subgraph, M.IsMatching ∧ M.verts ⊆ P ∪ F '' P ∧ M.edgeSet.encard = P.encard := by have hsep : ∀ a ∈ P, ∀ b ∈ P, F a ≠ b := fun a ha b hb h => hFD a ha (h ▸ hPD hb) let M : G.Subgraph := { verts := P ∪ F '' P Adj := fun v w => ∃ a ∈ P, (v = a ∧ w = F a) ∨ (v = F a ∧ w = a) adj_sub := by rintro v w ⟨a, ha, ⟨h1, h2⟩ | ⟨h1, h2⟩⟩ · rw [h1, h2]; exact hadjF a ha · rw [h1, h2]; exact (hadjF a ha).symm edge_vert := by rintro v w ⟨a, ha, ⟨h1, -⟩ | ⟨h1, -⟩⟩ · rw [h1]; exact Or.inl ha · rw [h1]; exact Or.inr ⟨a, ha, rfl⟩ symm := ⟨fun v w ⟨a, ha, h⟩ => ⟨a, ha, h.symm.imp (fun h => ⟨h.2, h.1⟩) (fun h => ⟨h.2, h.1⟩)⟩⟩ } have hMadj : ∀ v w, M.Adj v w ↔ ∃ a ∈ P, (v = a ∧ w = F a) ∨ (v = F a ∧ w = a) := fun v w => Iff.rfl refine ⟨M, ?_, subset_rfl, ?_⟩ · rintro v (hv | ⟨a, ha, rfl⟩) · refine ⟨F v, (hMadj _ _).2 ⟨v, hv, Or.inl ⟨rfl, rfl⟩⟩, fun y hy => ?_⟩ obtain ⟨a, ha, h⟩ := (hMadj _ _).1 hy rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h2, h1] · exact absurd h1.symm (hsep a ha v hv) · refine ⟨a, (hMadj _ _).2 ⟨a, ha, Or.inr ⟨rfl, rfl⟩⟩, fun y hy => ?_⟩ obtain ⟨b, hb, h⟩ := (hMadj _ _).1 hy rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 (hsep a ha b hb) · exact h2.trans (hinj hb ha h1.symm) · have hE : M.edgeSet = (fun a => s(a, F a)) '' P := by ext e induction e using Sym2.ind with | h v w => rw [SimpleGraph.Subgraph.mem_edgeSet, hMadj, Set.mem_image] constructor · rintro ⟨a, ha, h⟩ refine ⟨a, ha, ?_⟩ rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · rfl · exact Sym2.eq_swap · rintro ⟨a, ha, he⟩ refine ⟨a, ha, ?_⟩ rcases Sym2.eq_iff.1 he with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact Or.inl ⟨h1.symm, h2.symm⟩ · exact Or.inr ⟨h2.symm, h1.symm⟩ rw [hE] refine Set.InjOn.encard_image fun a ha b hb hab => ?_ rcases Sym2.eq_iff.1 hab with ⟨h1, -⟩ | ⟨h1, -⟩ · exact h1 · exact absurd h1.symm (hsep b hb a ha)/-- König's min-max theorem: the matching number equals the vertex cover number in any finite bipartite graph. -/theorem konig_matching_vertex_cover_num {V : Type*} [Fintype V] (G : SimpleGraph V) (h : G.IsBipartite) : graph_matching_num G = G.vertexCoverNum := by classical refine le_antisymm (graph_matching_num_le_vertex_cover_num G) ?_ obtain ⟨c⟩ := h obtain ⟨C, hCe, hC⟩ := G.vertexCoverNum_exists let A : Set V := {v | c v = 0} let B : Set V := {v | c v = 1} have h01 : ∀ x : Fin 2, x = 0 ∨ x = 1 := by decide have hdisj : Disjoint A B := by refine Set.disjoint_left.2 fun v ha hb => ?_ have h1 : c v = 0 := ha have h2 : c v = 1 := hb rw [h1] at h2 exact absurd h2 (by decide) have hAB : ∀ v, v ∈ A ∨ v ∈ B := fun v => h01 (c v) have hadj : ∀ ⦃v w⦄, G.Adj v w → (v ∈ A ∧ w ∈ B) ∨ (v ∈ B ∧ w ∈ A) := by intro v w hvw have hne := c.valid hvw rcases h01 (c v) with h1 | h1 <;> rcases h01 (c w) with h2 | h2 · exact absurd (h1.trans h2.symm) hne · exact Or.inl ⟨h1, h2⟩ · exact Or.inr ⟨h1, h2⟩ · exact absurd (h1.trans h2.symm) hne have hadj' : ∀ ⦃v w⦄, G.Adj v w → (v ∈ B ∧ w ∈ A) ∨ (v ∈ A ∧ w ∈ B) := fun v w h => (hadj h).symm obtain ⟨FA, hFAi, hFA⟩ := bipartite_min_cover_side_inj_neighbors G A B C hdisj hadj hC hCe obtain ⟨FB, hFBi, hFB⟩ := bipartite_min_cover_side_inj_neighbors G B A C hdisj.symm hadj' hC hCe obtain ⟨MA, hMA, hvA, heA⟩ := subgraph_matching_of_injOn_neighbors G (A ∩ C) C FA hFAi (fun a ha => (hFA a ha).2.2) Set.inter_subset_right (fun a ha => (hFA a ha).2.1) obtain ⟨MB, hMB, hvB, heB⟩ := subgraph_matching_of_injOn_neighbors G (B ∩ C) C FB hFBi (fun a ha => (hFB a ha).2.2) Set.inter_subset_right (fun a ha => (hFB a ha).2.1) have hd : Disjoint MA.verts MB.verts := by refine Set.disjoint_left.2 fun v hva hvb => ?_ rcases hvA hva with hv1 | ⟨a, ha, rfl⟩ <;> rcases hvB hvb with hv2 | ⟨b, hb, hv2⟩ · exact Set.disjoint_left.1 hdisj hv1.1 hv2.1 · exact (hFB b hb).2.1 (by rw [hv2]; exact hv1.2) · exact (hFA a ha).2.1 hv2.2 · exact Set.disjoint_left.1 hdisj (by rw [← hv2]; exact (hFB b hb).1) (hFA a ha).1 obtain ⟨hM, hcard⟩ := isMatching_sup_disjoint_encard MA MB hMA hMB hd have hCsplit : C = (A ∩ C) ∪ (B ∩ C) := by ext v constructor · intro hv rcases hAB v with h | h · exact Or.inl ⟨h, hv⟩ · exact Or.inr ⟨h, hv⟩ · rintro (⟨-, hv⟩ | ⟨-, hv⟩) <;> exact hv have hCdisj : Disjoint (A ∩ C) (B ∩ C) := hdisj.mono Set.inter_subset_left Set.inter_subset_left calc G.vertexCoverNum = C.encard := hCe.symm _ = (A ∩ C).encard + (B ∩ C).encard := by rw [← Set.encard_union_eq hCdisj, ← hCsplit] _ = (MA ⊔ MB).edgeSet.encard := by rw [hcard, heA, heB] _ ≤ graph_matching_num G := le_iSup₂ (f := fun (M : G.Subgraph) (_ : M.IsMatching) => M.edgeSet.encard) (MA ⊔ MB) hM