op_1058_of_diam_le_two
For any finite connected simple graphs G and H of diameter at most 2, if at least one of G and H is well-covered, then at least one of G and H has the well-covered powers property.
Statement
theorem op_1058_of_diam_le_two {V W : Type*} [Fintype V] [Fintype W] (G : SimpleGraph V) (H : SimpleGraph W) (hG : G.Connected) (hH : H.Connected) (hdG : G.diam ≤ 2) (hdH : H.diam ≤ 2) (hwc : simple_graph_is_well_covered G ∨ simple_graph_is_well_covered H) : simple_graph_has_well_covered_powers G ∨ simple_graph_has_well_covered_powers H
- Related work
- arXiv:2611.03956 Question 1.1
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_has_well_covered_powersA finite simple graph G has the well-covered powers property if for every integer d ≥ 1, the d-th graph power G^d is well-covered.
- forall_power_well_covered_of_well_covered_diam_le_twoLet G be a finite connected well-covered graph of diameter at most 2. Then G^d is well-covered for every d ≥ 1.
- 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…
Read back from the Lean
Let V and W be finite types. Let G be a simple graph on V and H be a simple graph on W. Assume that:
1. G is connected (G.Connected),
2. H is connected (H.Connected),
3. the diameter of G is at most 2 (G.diam ≤ 2),
4. the diameter of H is at most 2 (H.diam ≤ 2), and
5. G is well-covered or H is well-covered (simple_graph_is_well_covered G ∨ simple_graph_is_well_covered H).
Then G has well-covered powers or H has well-covered powers (simple_graph_has_well_covered_powers G ∨ simple_graph_has_well_covered_powers H).
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 splits into cases on the assumption that at least one of G or H is well-covered. In each branch, the well-covered factor is finite, connected, and has diameter at most 2, so an established lemma immediately yields that all of its graph powers are well-covered. Thus, at least one of the two graphs has well-covered powers.
If G is well-covered, then G has well-covered powers, satisfying the disjunction.
We perform case analysis on the hypothesis hwc, which asserts that at least one of G or H is well-covered. In the first case, G is well-covered (hG_wc). To prove the disjunction, it suffices to prove the left alternative, namely that G has well-covered powers. Since G is finite, connected (hG), has diameter at most 2 (hdG), and is well-covered (hG_wc), the lemma forall_power_well_covered_of_well_covered_diam_le_two applies directly to establish that G has well-covered powers.
uses
forall_power_well_covered_of_well_covered_diam_le_twocases hwc with | inl hG_wc => left exact forall_power_well_covered_of_well_covered_diam_le_two G hG hdG hG_wc
If H is well-covered, then H has well-covered powers, satisfying the disjunction.
In the second case, H is well-covered (hH_wc). It suffices to prove the right alternative, namely that H has well-covered powers. Applying forall_power_well_covered_of_well_covered_diam_le_two to H, using its connectedness (hH), diameter bound (hdH), and well-coveredness (hH_wc), establishes that H has well-covered powers.
uses
forall_power_well_covered_of_well_covered_diam_le_two| inr hH_wc => right exact forall_power_well_covered_of_well_covered_diam_le_two H hH hdH hH_wc
forall_power_well_covered_of_well_covered_diam_le_two- If a finite simple graph is connected, has diameter at most 2, and is well-covered, then each of its powers Gᵈ (for d ≥ 1) is also well-covered.
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.
/-- For graphs of diameter at most 2, if at least one factor is well-covered, then at least one factor has well-covered powers. -/theorem op_1058_of_diam_le_two {V W : Type*} [Fintype V] [Fintype W] (G : SimpleGraph V) (H : SimpleGraph W) (hG : G.Connected) (hH : H.Connected) (hdG : G.diam ≤ 2) (hdH : H.diam ≤ 2) (hwc : simple_graph_is_well_covered G ∨ simple_graph_is_well_covered H) : simple_graph_has_well_covered_powers G ∨ simple_graph_has_well_covered_powers H := by cases hwc with | inl hG_wc => left exact forall_power_well_covered_of_well_covered_diam_le_two G hG hdG hG_wc | inr hH_wc => right exact forall_power_well_covered_of_well_covered_diam_le_two H hH hdH hH_wc