AFTD Auto-Formalizing Theoretical Domains

bipartite_well_covered_exists_perfect_matching_ravindra

theoremverified

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
Used by 1

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.

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

    line 7

    uses bipartite_well_covered_has_perfect_matching

      obtain ⟨M, hM⟩ := bipartite_well_covered_has_perfect_matching G hconn hbip hcard hwc
  2. The 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.

    lines 8–9

    uses bipartite_well_covered_perfect_matching_ravindra

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

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