bipartite_well_covered_exists_perfect_matching_ravindra
Every 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, every neighbor of u is adjacent to every neighbor of v (N(u) x N(v) are all edges).
Statement
theorem bipartite_well_covered_exists_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, M.IsPerfectMatching ∧ ∀ u v : V, M.Adj u v → ∀ x y : V, G.Adj u x → G.Adj v y → G.Adj x y
- Source
- step towards bipartite_all_powers_well_covered_diameter_le_two
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- bipartite_well_covered_has_perfect_matchingEvery finite connected well-covered bipartite graph G with at least 2 vertices has a perfect matching.
- bipartite_well_covered_perfect_matching_ravindraIn 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…
- 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…
- Used by 1
- bipartite_all_powers_well_covered_diameter_le_twoEvery finite connected bipartite simple graph G with at least two vertices whose positive integer powers G^d (for d ≥ 1) are all…
The proof, explained
The existence of Ravindra's matching follows by combining two existing theorems. First, any finite connected well-covered bipartite graph with at least two vertices admits a perfect matching. Second, every perfect matching in such a graph satisfies Ravindra's property: the neighborhood of one endpoint of any matching edge is completely joined to the neighborhood of the other endpoint.
There exists a perfect matching M in G.
We invoke `bipartite_well_covered_has_perfect_matching` with the hypotheses that G is connected, bipartite, has at least two vertices, and is well-covered, obtaining a subgraph M and a proof hM that M is a perfect matching of G.
uses
bipartite_well_covered_has_perfect_matchingobtain ⟨M, hM⟩ := bipartite_well_covered_has_perfect_matching G hconn hbip hcard hwcThe matching M is a perfect matching whose edges have complete bipartite neighborhoods, completing the proof.
We provide M and its certificate of being a perfect matching hM as the witness. For the second conjunct, given any edge uv in M and any vertices x, y with x adjacent to u and y adjacent to v in G, we apply `bipartite_well_covered_perfect_matching_ravindra` to conclude that x and y are adjacent in G.
uses
bipartite_well_covered_perfect_matching_ravindraexact ⟨M, hM, fun u v huv x y hx hy => bipartite_well_covered_perfect_matching_ravindra G hconn hbip hcard hwc M hM u v huv x y hx hy⟩
bipartite_well_covered_has_perfect_matching- In a finite connected well-covered bipartite graph with at least two vertices, there exists a perfect matching.
bipartite_well_covered_perfect_matching_ravindra- In a finite connected well-covered bipartite graph with at least two vertices, every perfect matching satisfies Ravindra's condition: for every edge uv in the matching, every neighbor of u is adjacent to every neighbor of 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.
/-- Ravindra's theorem (1977): Every finite connected well-covered bipartite graph with at least 2 vertices has a perfect matching M whose edges have complete bipartite neighborhoods. -/theorem bipartite_well_covered_exists_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, M.IsPerfectMatching ∧ ∀ u v : V, M.Adj u v → ∀ x y : V, G.Adj u x → G.Adj v y → G.Adj x y := by obtain ⟨M, hM⟩ := bipartite_well_covered_has_perfect_matching G hconn hbip hcard hwc exact ⟨M, hM, fun u v huv x y hx hy => bipartite_well_covered_perfect_matching_ravindra G hconn hbip hcard hwc M hM u v huv x y hx hy⟩