simple_graph_is_well_covered
def
A finite graph is well-covered if all its maximal independent sets have the same cardinality (equivalently, all its minimal vertex covers have the same cardinality, since I is a maximal independent set iff V ∖ I is a minimal vertex cover).
Statement
def simple_graph_is_well_covered {V : Type*} [Fintype V] (G : SimpleGraph V) : Prop
- Defined in
- arXiv:2610.09300 (On graphs whose powers are well-covered), Sec. 2 (well-covered: all minimal vertex covers have the same size; the paper notes the equivalence with maximal independent sets used here).
- Verified
- 11 Oct 2026
- Axioms
- none listed
- Used by 28
- simple_graph_is_well_covered_botThe edgeless graph on a finite vertex set is well-covered (its only maximal independent set is the whole vertex set).
- simple_graph_power_well_covered_not_ball_union_subsetLet G be a finite graph and d ≥ 1 with G^d well-covered. Then there are no vertices s, t, w with d_G(s, t) ≥ d + 1 and B_d(s) ∪ B_d(t) ⊆…
- complete_bipartite_two_two_all_powers_well_coveredFor every positive integer d, the d-th power of the complete bipartite graph K_{2,2} is well-covered.
- 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_well_covered_has_perfect_matchingEvery finite connected well-covered bipartite graph G with at least 2 vertices has a perfect matching.
- 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…
- 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…
- diam_le_one_of_forall_power_well_covered_of_degree_eq_oneIf a finite connected graph G has a vertex of degree 1 and G^d is well-covered for every d ≥ 1, then diam(G) ≤ 1 (G is K_2). In particular…
- 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.
- cycle_seven_power_one_well_coveredThe first power (the graph itself) of the 7-cycle graph is well-covered.
- exists_planar_all_powers_well_covered_diam_eq_threeThere exists a finite connected simple planar graph G with at least two vertices whose diameter is exactly 3 and such that every positive…
- cycle_five_all_powers_well_coveredFor every positive integer d, the d-th power of the 5-cycle graph C_5 is well-covered.
- forall_power_well_covered_iff_clique_blowupLet G be a finite simple graph and a_1, …, a_n positive integers, H = G[K_{a_1}, …, K_{a_n}] its clique blow-up. Then G^d is well-covered…
- cycle_seven_all_powers_well_coveredFor every positive integer d, the d-th power of the 7-cycle graph C_7 is well-covered.
- simple_graph_power_well_covered_iff_clique_blowupFor every d ≥ 1 and positive integers a_i, G^d is well-covered iff H^d is well-covered, where H = G[K_{a_1}, …, K_{a_n}].
- not_planar_all_powers_well_covered_characterizationIt is not the case that every finite connected simple planar graph G with at least two vertices whose powers G^d are all well-covered is…
- forall_power_well_covered_of_well_covered_diam_le_threeLet G be a finite connected simple graph of diameter at most 3. If G and its second power G^2 are both well-covered, then every positive…
- cycle_seven_power_ge_three_well_coveredEvery power d ≥ 3 of the 7-cycle graph is well-covered: since diam(C_7) = 3 ≤ d, the d-th power is the complete graph K_7 and every…
- exists_connected_all_powers_well_covered_diam_geFor every positive integer D, there exists a finite connected simple graph G with diameter at least D such that every positive power G^d…
- bipartite_all_powers_well_covered_diameter_le_twoEvery finite connected bipartite simple graph G with at least two vertices whose positive integer powers G^d (for d ≥ 1) are all…
- simple_graph_eccent_eq_diam_of_power_well_coveredLet G be a finite connected graph of diameter D ≥ 2 such that G^{D−1} is well-covered. Then every vertex of G has eccentricity D (G is…
- simple_graph_no_leaf_of_power_well_coveredLet G be a finite connected graph of diameter D ≥ 2 such that G^{D−1} is well-covered. Then G has no leaves (no vertex of degree 1).
- exists_triangle_free_all_powers_well_covered_diam_eq_threeThere exists a finite connected triangle-free simple graph G with at least two vertices whose diameter is exactly 3 and such that every…
- bipartite_well_covered_perfect_matching_ravindraIn any finite connected well-covered bipartite graph G with at least 2 vertices, for any perfect matching M and any edge uv of M, every…
- 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.
- cycle_seven_power_two_well_coveredThe square of the 7-cycle graph is well-covered: all maximal independent sets have size 2.
- boxProd_completeGraph_all_powers_well_coveredLet G be a finite connected nontrivial graph, and let t be an integer with t > |V(G)|. If every positive power G^d (d ≥ 1) is…
- complete_graph_two_all_powers_well_coveredThe complete graph on 2 vertices K_2 is connected, has diameter 1, and every positive power K_2^d (d ≥ 1) is well-covered.
Lean source view module on GitHub
def simple_graph_is_well_covered {V : Type*} [Fintype V] (G : SimpleGraph V) : Prop := ∀ s t : Finset V, Maximal (fun u : Finset V => G.IsIndepSet (u : Set V)) s → Maximal (fun u : Finset V => G.IsIndepSet (u : Set V)) t → s.card = t.card