simple_graph_has_well_covered_powers
def
A 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.
Statement
def simple_graph_has_well_covered_powers {V : Type*} [Fintype V] (G : SimpleGraph V) : Prop
- Defined in
- arXiv:2611.03956 Def 2.2
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Built on 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…
- Used by 2
- op_1058_of_diam_le_twoFor 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…
- cycle_five_has_well_covered_powersThe 5-cycle graph C_5 has the well-covered powers property.
Read back from the Lean
Given a finite type $V$ and a simple graph $G$ on $V$, the predicate simple_graph_has_well_covered_powers G asserts that for every natural number $d \ge 1$, the $d$-th graph power of $G$ is well-covered (that is, all maximal independent sets of vertices in the $d$-th power of $G$ have the same cardinality).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A finite simple graph has the well-covered powers property if every positive power G^d is well-covered. -/ def simple_graph_has_well_covered_powers {V : Type*} [Fintype V] (G : SimpleGraph V) : Prop := ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)