AFTD Auto-Formalizing Theoretical Domains

konig_matching_vertex_cover_num

theoremverifiedformalization

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

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.

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

    lines 8–11

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

    lines 12–24

    uses bipartite_hall_step_is_vertex_cover

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

    lines 25–37

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

    lines 38–50

    uses Finset.card_union_le, Finset.card_sdiff_add_card_eq_card, Finset.card_map, le_trans

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

    lines 51–61

    uses Finset.all_card_le_biUnion_card_iff_exists_injective, dif_pos, congrArg

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

    lines 69–84

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

    lines 85–96

    uses subset_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)
  8. 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.

    lines 97–117

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

    lines 122–125

    uses le_antisymm, graph_matching_num_le_vertex_cover_num

      classical
      refine le_antisymm (graph_matching_num_le_vertex_cover_num G) ?_
      obtain ⟨c⟩ := h
      obtain ⟨C, hCe, hC⟩ := G.vertexCoverNum_exists
  10. 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.

    lines 126–145

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

    lines 146–151

    uses bipartite_min_cover_side_inj_neighbors, subgraph_matching_of_injOn_neighbors, Set.inter_subset_right

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

    lines 152–159

    uses isMatching_sup_disjoint_encard

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

    lines 160–174

    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

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