AFTD Auto-Formalizing Theoretical Domains

bipartite_all_powers_well_covered_diameter_le_two

theoremverifiedformalization

Every finite connected bipartite simple graph G with at least two vertices whose positive integer powers G^d (for d ≥ 1) are all well-covered has diameter at most 2.

Statement

theorem bipartite_all_powers_well_covered_diameter_le_two :
    ∀ {V : Type*} [Fintype V] (G : SimpleGraph V),
      G.Connected →
      G.IsBipartite →
      2 ≤ Fintype.card V →
      (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)) →
      G.diam ≤ 2
Formalizes
arXiv:2610.09300, Theorem 1.3
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

Read back from the Lean

For every finite type $V$ and every simple graph $G$ on $V$: if $G$ is connected, $G$ is bipartite, $V$ has at least 2 vertices, and for every natural number $d \ge 1$ the $d$-th graph power of $G$ is well-covered (meaning all inclusion-maximal independent finsets of vertices in the power graph have the same cardinality), then the diameter of $G$ is at most 2.

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

The proof combines two established structural results about well-covered bipartite graphs. First, because all powers are well-covered, the graph $G = G^1$ is well-covered; by Ravindra's theorem, it admits a perfect matching with an edge-completion property on neighbors. Second, applying the known theorem that a connected bipartite graph with such a Ravindra matching whose square $G^2$ is well-covered must have diameter at most 2 directly finishes the proof.

  1. Fix a finite connected bipartite graph $G$ on at least two vertices whose positive powers $G^d$ ($d \ge 1$) are all well-covered.

    We introduce the vertex type $V$ (with its finite instance), the graph $G$, and the hypotheses: connectivity (`hconn`), bipartiteness (`hbip`), the cardinality condition $|V| \ge 2$ (`hcard`), and the assumption that every power $G^d$ for $d \ge 1$ is well-covered (`hpow`).

    line 9

      intro V _ G hconn hbip hcard hpow
  2. $G$ itself is well-covered.

    Specializing the hypothesis that all positive powers are well-covered to $d = 1$ (noting $1 \le 1$ by reflexivity `le_rfl`), the power $G^1$ is well-covered. Since the first power $G^1$ is identical to $G$ (`simple_graph_power_one`), this shows $G$ is well-covered.

    lines 10–12

    uses simple_graph_power_one, le_rfl

      have hwc : simple_graph_is_well_covered G := by
        rw [← simple_graph_power_one G]
        exact hpow 1 le_rfl
  3. $G$ possesses a Ravindra perfect matching: a perfect matching $M$ such that whenever $uv \in M$, $u \sim x$, and $v \sim y$, we have $x \sim y$.

    By Ravindra's theorem for bipartite graphs (`bipartite_well_covered_exists_perfect_matching_ravindra`), any finite connected bipartite well-covered graph with at least two vertices has such a perfect matching.

    lines 13–14

    uses bipartite_well_covered_exists_perfect_matching_ravindra

      obtain ⟨M, hM, hrav⟩ :=
        bipartite_well_covered_exists_perfect_matching_ravindra G hconn hbip hcard hwc
  4. The diameter of $G$ is at most 2.

    By `bipartite_ravindra_matching_power_two_well_covered_diam_le_two`, any connected bipartite graph with a Ravindra perfect matching whose square $G^2$ is well-covered has diameter at most 2. The well-coveredness of $G^2$ is obtained by specializing the power hypothesis to $d = 2$, with $1 \le 2$ verified by numerical evaluation.

    lines 15–16

    uses bipartite_ravindra_matching_power_two_well_covered_diam_le_two

      exact bipartite_ravindra_matching_power_two_well_covered_diam_le_two G hconn hbip M hM hrav
        (hpow 2 (by norm_num))
simple_graph_power_one
The first power $G^1$ of a graph $G$ is equal to $G$ itself.
le_rfl
The inequality relation $\le$ is reflexive ($a \le a$ for any $a$).
bipartite_well_covered_exists_perfect_matching_ravindra
Every finite connected bipartite well-covered graph with at least two vertices admits a perfect matching $M$ satisfying the Ravindra property: whenever $uv \in M$ is a matching edge and $u \sim x$, $v \sim y$ in $G$, the edge $xy$ is also in $G$.
bipartite_ravindra_matching_power_two_well_covered_diam_le_two
If a connected bipartite graph admits a perfect matching satisfying the Ravindra property and its square $G^2$ is well-covered, then its diameter is at most 2.

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

/-- Every connected bipartite graph with at least two vertices whose powers are all well-covered has diameter at most 2. -/theorem bipartite_all_powers_well_covered_diameter_le_two :    ∀ {V : Type*} [Fintype V] (G : SimpleGraph V),      G.Connected →      G.IsBipartite →      2 ≤ Fintype.card V →      (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)) →      G.diam ≤ 2 := by  intro V _ G hconn hbip hcard hpow  have hwc : simple_graph_is_well_covered G := by    rw [← simple_graph_power_one G]    exact hpow 1 le_rfl  obtain ⟨M, hM, hrav⟩ :=    bipartite_well_covered_exists_perfect_matching_ravindra G hconn hbip hcard hwc  exact bipartite_ravindra_matching_power_two_well_covered_diam_le_two G hconn hbip M hM hrav    (hpow 2 (by norm_num))
See it in the graphDiscuss this resultChallenge it