AFTD Auto-Formalizing Theoretical Domains

bipartite_hall_step_is_vertex_cover

theoremverified

In 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 vertex cover of G.

Statement

theorem bipartite_hall_step_is_vertex_cover {V : Type*} (G : SimpleGraph V) (A B C S : 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) (hS : S ⊆ A ∩ C) :
    G.IsVertexCover ((C \ S) ∪ {b ∈ B \ C | ∃ a ∈ S, G.Adj a b})
Source
step towards konig_matching_vertex_cover_num
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To show that replacing a subset S ⊆ A ∩ C in a vertex cover C with its neighbors N(S) ∩ (B \ C) yields another vertex cover, we consider an arbitrary edge. By bipartiteness and symmetry, it suffices to show that any edge between x ∈ A and y ∈ B is covered. Since C is a vertex cover, at least one endpoint is in C: if y ∈ C, disjointness of A and B prevents y from belonging to S, so y ∈ C \ S; if y ∉ C, then x ∈ C, and either x ∉ S (so x ∈ C \ S) or x ∈ S (which places y into N(S) ∩ (B \ C)). In all cases, at least one endpoint is in the new set.

  1. To show that the modified set is a vertex cover, it suffices to show that an arbitrary edge has at least one endpoint in it.

    Fix an arbitrary pair of adjacent vertices v and w in G. By definition of a vertex cover, we must show that at least one of v or w belongs to (C \ S) ∪ {b ∈ B \ C | ∃ a ∈ S, G.Adj a b}.

    line 7

      intro v w hvw
  2. For any edge between x ∈ A and y ∈ B, if y ∈ C, then y is in the new vertex cover.

    We set up an auxiliary lemma h_dir asserting that any edge directed from A to B is covered by the new set. Given adjacent vertices x ∈ A and y ∈ B, we split into cases on whether y ∈ C. If y ∈ C, we show y ∈ C \ S. If y were in S, then since S ⊆ A, y would belong to A ∩ B, contradicting the assumption that A and B are disjoint (Set.disjoint_iff.mp). Hence y ∉ S, so y ∈ C \ S, placing y in the new vertex cover.

    lines 8–15

    uses Set.disjoint_iff.mp

      have h_dir : ∀ {x y : V}, G.Adj x y → x ∈ A → y ∈ B →
          x ∈ (C \ S) ∪ {b ∈ B \ C | ∃ a ∈ S, G.Adj a b} ∨
          y ∈ (C \ S) ∪ {b ∈ B \ C | ∃ a ∈ S, G.Adj a b} := by
        intro x y hxy hxA hyB
        by_cases hyC : y ∈ C
        · right
          left
          exact ⟨hyC, fun hyS => Set.disjoint_iff.mp hdisj ⟨(hS hyS).1, hyB⟩⟩
  3. For any edge between x ∈ A and y ∈ B, if y ∉ C, then at least one endpoint is in the new vertex cover, completing the auxiliary lemma.

    If y ∉ C, then because C is a vertex cover of G, the edge between x and y must have at least one endpoint in C; since y ∉ C, we have x ∈ C by disjunctive syllogism (resolve_right). We then split on whether x ∈ S: if x ∈ S, then y is a neighbor in B \ C of a vertex in S, so y belongs to {b ∈ B \ C | ∃ a ∈ S, G.Adj a b}; if x ∉ S, then x ∈ C \ S. In either case, one of the endpoints is in the new set, which establishes h_dir.

    lines 16–23

    uses resolve_right

        · have hxC : x ∈ C := (hC hxy).resolve_right hyC
          by_cases hxS : x ∈ S
          · right
            right
            exact ⟨⟨hyB, hyC⟩, x, hxS, hxy⟩
          · left
            left
            exact ⟨hxC, hxS⟩
  4. The edge between v and w is covered by the new set, so the set is a vertex cover.

    By the bipartiteness hypothesis, the edge between v and w has either v ∈ A and w ∈ B, or v ∈ B and w ∈ A. In the first case, h_dir directly shows that v or w is in the new set. In the second case, by symmetry of adjacency (G.adj_symm), w is adjacent to v with w ∈ A and v ∈ B; applying h_dir shows that w or v is in the new set, and swapping the disjunction concludes the proof.

    lines 24–26

    uses G.adj_symm

      rcases hadj hvw with ⟨hvA, hwB⟩ | ⟨hvB, hwA⟩
      · exact h_dir hvw hvA hwB
      · exact (h_dir (G.adj_symm hvw) hwA hvB).symm
Set.disjoint_iff.mp
If two sets are disjoint, their intersection is empty (a subset of the empty set).
resolve_right
Given a disjunction P ∨ Q and the negation ¬Q, the disjunct P holds.
G.adj_symm
Adjacency in a simple graph is symmetric: if v is adjacent to w, then w is adjacent to v.

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, replacing a subset S of a vertex cover C in partition A with its neighbors in partition B outside C preserves the vertex cover property. -/theorem bipartite_hall_step_is_vertex_cover {V : Type*} (G : SimpleGraph V) (A B C S : 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) (hS : S ⊆ A ∩ C) :    G.IsVertexCover ((C \ S) ∪ {b ∈ B \ C | ∃ a ∈ S, G.Adj a b}) := by  intro v w hvw  have h_dir : ∀ {x y : V}, G.Adj x y → x ∈ A → y ∈ B →      x ∈ (C \ S) ∪ {b ∈ B \ C | ∃ a ∈ S, G.Adj a b} ∨      y ∈ (C \ S) ∪ {b ∈ B \ C | ∃ a ∈ S, G.Adj a b} := by    intro x y hxy hxA hyB    by_cases hyC : y ∈ C    · right      left      exact ⟨hyC, fun hyS => Set.disjoint_iff.mp hdisj ⟨(hS hyS).1, hyB⟩⟩    · have hxC : x ∈ C := (hC hxy).resolve_right hyC      by_cases hxS : x ∈ S      · right        right        exact ⟨⟨hyB, hyC⟩, x, hxS, hxy⟩      · left        left        exact ⟨hxC, hxS⟩  rcases hadj hvw with ⟨hvA, hwB⟩ | ⟨hvB, hwA⟩  · exact h_dir hvw hvA hwB  · exact (h_dir (G.adj_symm hvw) hwA hvB).symm
See it in the graphDiscuss this resultChallenge it