Well-covered graph¶
A finite simple graph in which every inclusion-maximal independent vertex set has the same size.
Core Idea¶
A well-covered graph is a finite simple undirected graph in which every inclusion-maximal independent vertex set has the same number of vertices.[ref-d261d11829be][ref-e499f19acfb2] Independent means no selected pair is adjacent; maximal means no further vertex can be added while preserving independence. Maximum instead means largest possible. The property concerns the whole graph and every maximal set, not one chosen optimum.
Scope of Application¶
The condition applies to finite simple undirected graphs; its source-presented positives include a path and an odd cycle.
- Path graphs — test the four-vertex path P4's maximal independent sets.[^ref-d261d11829be]
- Cycle graphs — test the seven-vertex cycle C7's maximal independent sets.[^ref-d261d11829be]
- Graphs with isolates — apply the same criterion without automatically excluding isolated vertices.[^ref-e499f19acfb2]
- Minimal-cover comparison — translate the condition by complementing maximal independent sets.[^ref-e499f19acfb2]
Clarity¶
A set can be maximal without being maximum. In the three-vertex path P3, the center alone is maximal, while the two endpoints form a larger maximal set. Their sizes differ, so P3 is not well-covered. This direct counterexample exposes why finding one largest set proves too little.
Manages Complexity¶
Track four things: the graph, independent subsets, which subsets cannot be extended, and their sizes. For the source-presented P4 and C7 graphs,[^ref-d261d11829be] direct finite checks leave three maximal pairs and seven maximal triples respectively. Those counts are the entry's derivations, not printed lists claimed from Hartnell.
Abstract Reasoning¶
Use counterexample search and complete comparison: two maximal sets of unequal sizes refute the property, while a positive proof must account for every maximal set. Equal sizes then imply that each maximal set is maximum, since a finite graph has a maximum independent set that is also maximal.
Knowledge Transfer¶
The same test transfers from an acyclic path to a leafless odd cycle.[^ref-d261d11829be] Minimal vertex covers give a within-domain translation under the graph's conventions,[^ref-e499f19acfb2] not an extra requirement. Maximal Independent Set names one subset; well-coveredness is the all-sets condition on its graph. Neither broad invariance vocabulary nor these two examples establish a substrate-neutral parent or unrestricted claims about graph products, games or algorithm speed.
Neighborhood in Abstraction Space¶
Well-covered graph sits in a sparse region of the domain-specific corpus (73rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Extremal Graph Theory & Bounds (7 abstractions)
Nearest neighbors
- Maximal independent set — 0.85
- Clique (Graph Theory) — 0.83
- Clique graph — 0.83
- Degree diameter problem — 0.83
- Connected Dominating Set — 0.83
Computed from structural-signature embeddings · 2026-10-17
References¶
[^ref-d261d11829be]: B. L. Hartnell. (1999). Well-Covered Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing 29:107–115, printed p. 107 opening overview. The publisher-hosted PDF was reachable, but automated full-PDF text extraction yielded no page text; the searchable opening directly supplied the definition and named P4/C7 examples with sizes. Complete maximal-set enumerations above are independently checked finite derivations, not claims about printed lists. Its searchable P3 sentence was truncated, so the P3 counterexample above rests on direct finite proof. [^ref-e499f19acfb2]: Iván D. Castrillón, Roberto Cruz, and Enrique Reyes. (2016). On well-covered, vertex decomposable and Cohen-Macaulay graphs. Electronic Journal of Combinatorics 23(2):P2.39. Full original publisher PDF, pp. 1–2 Introduction for the simple-graph definition and minimal-cover/unmixed translations, and p. 6 Definition 16 for the distinct very-well-covered class. The algebraic statements use the paper's conventions.