bipartite_all_powers_well_covered_diameter_le_two
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
- bipartite_well_covered_exists_perfect_matching_ravindraEvery 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,…
- bipartite_ravindra_matching_power_two_well_covered_diam_le_twoIf a finite connected bipartite simple graph G admits a perfect matching M with complete bipartite neighborhoods and its second power G^2…
- simple_graph_powerThe d-th power G^d of a graph G: same vertices, two distinct vertices adjacent iff they are joined by a path (equivalently a walk) of…
- 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…
- simple_graph_power_oneG^1 = G.
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.
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`).
intro V _ G hconn hbip hcard hpow$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.
uses
simple_graph_power_one,le_rflhave hwc : simple_graph_is_well_covered G := by rw [← simple_graph_power_one G] exact hpow 1 le_rfl
$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.
uses
bipartite_well_covered_exists_perfect_matching_ravindraobtain ⟨M, hM, hrav⟩ := bipartite_well_covered_exists_perfect_matching_ravindra G hconn hbip hcard hwcThe 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.
uses
bipartite_ravindra_matching_power_two_well_covered_diam_le_twoexact 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.
- Although the hypothesis assumes all positive integer powers $G^d$ ($d \ge 1$) are well-covered, the proof only ever uses the cases $d = 1$ (to obtain the Ravindra matching) and $d = 2$ (to bound the diameter).
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.
/-- 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))