bipartite_hall_step_is_vertex_cover
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
- konig_matching_vertex_cover_numKönig's theorem: in any finite bipartite simple graph G, the matching number is equal to the vertex cover number.
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.
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}.
intro v w hvwFor 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.
uses
Set.disjoint_iff.mphave 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⟩⟩
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.
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⟩
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.
uses
G.adj_symmrcases 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
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, 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