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 cardinality.[1][2] An independent set contains no adjacent pair. It is maximal when no further vertex can be added without losing independence; it is maximum when no larger independent set exists anywhere in the graph. In a well-covered graph every maximal independent set is maximum, but merely finding one maximum set does not establish that the graph is well-covered.
This is a condition on an entire graph and all of its maximal independent sets. It neither describes one chosen set nor requires an algorithm that finds the sets. The four-vertex path and seven-vertex cycle below are source-presented, structurally different instances of the same class.[1]
Structural Signature¶
- Declared finite graph — Fix a simple undirected vertex set and adjacency relation. Without that carrier, neither independence nor the class condition is defined.[2]
- Independent subsets — Consider only vertex subsets containing no adjacent pair. Arbitrary subsets would change the objects being tested.[2]
- Inclusion-maximality — Retain each independent set that cannot be extended by another vertex. Checking only a largest set would overlook a smaller unextendible set, as the three-vertex path shows.
- Equal size across all maximal sets — Compare the cardinalities of every retained set. One unequal pair refutes well-coveredness; equality across the full family establishes it.[1][2]
The word every does the main work. Because a maximum independent set exists in any finite graph and is maximal, equal sizes of all maximal sets make each one maximum. The reverse inference from one maximum set to equal sizes is invalid.
What It Is Not¶
Well-coveredness is not the property of an individual maximal independent set. A graph may contain one maximum set and also a smaller maximal set. Nor is it certified by a single successful greedy run: one run reaches only one maximal set, while the definition quantifies over all of them.
It is not the same as a well-colored graph, whose all-order condition concerns the number of colors used by greedy vertex coloring. It is also weaker than the cited very-well-covered condition, which adds constraints including the absence of isolated vertices. Ordinary well-coveredness does not exclude an isolated vertex merely for being isolated.[2]
Scope of Application¶
The literal setting is finite simple undirected graph classification. It includes paths and cycles when they pass the all-maximal-set test: Hartnell names the four-vertex path and seven-vertex cycle as positive examples.[1] Graphs with isolated vertices remain within the definition; their status is decided by the same universal condition.[2]
The complement of a maximal independent set is a minimal vertex cover. Thus equal size across maximal independent sets translates to equal size across minimal vertex covers of the same finite graph. The cited algebraic literature also describes an unmixed edge-ideal formulation under its conventions.[2] These are alternate descriptions of the graph condition, not extra requirements or additional worked graphs. No general claim about graph products, game outcomes, recognition complexity, or Cohen–Macaulayness follows from the two examples.
Clarity¶
Maximal means no permitted one-vertex extension; maximum means largest cardinality over all independent sets. The three-vertex path makes the difference visible. Its center vertex alone forms a maximal independent set of size one, because both endpoints touch it. Its two endpoints form another maximal independent set of size two. One set is maximum, yet the graph is not well-covered because the two maximal sets have different sizes.
The distinction also explains the class name. “Well-covered” is an established graph-theoretic label, not a promise that the graph has a particular number of vertices in a cover. The minimal-cover translation follows by taking complements and retaining the graph's own vertex count.[2]
Manages Complexity¶
A graph can have many independent sets, so test the property in a fixed order: declare the graph, exclude subsets with adjacent vertices, keep only unextendible independent subsets, and compare their sizes. This sequence avoids mixing feasible sets with maximal ones and avoids treating one optimum as evidence about every local endpoint.
For the path P4, the last two steps leave three maximal sets, all of size two. For the cycle C7, direct enumeration leaves seven maximal sets, all of size three. Those enumerations are finite checks performed for this entry; Hartnell's opening names the graphs and gives their maximal-set sizes, but the available searchable passage does not print the complete lists.[1]
Abstract Reasoning¶
One smaller maximal independent set is a complete counterexample to well-coveredness. It is unnecessary to inspect every other set once a pair of unequal maximal sizes has been proved, as P3 demonstrates. Conversely, proving the positive class requires covering all maximal sets, either by exhaustive enumeration for a small graph or by a general structural argument for a larger family.
The condition has a useful logical direction: uniform maximal-set size implies that every maximal set reaches the independence number. The existence of a maximum set alone does not imply uniformity. This inference is definitional, not an empirical claim about a particular algorithm's speed or output.
Knowledge Transfer¶
The same test applies to unlike graph shapes. Hartnell presents a four-vertex path and a seven-vertex cycle as well-covered.[1] Their different adjacency patterns fill the four roles in the Structural Signature. What transfers is the finite-graph test, not the path's or cycle's particular set list.
Vertex-cover and edge-ideal formulations can help translate a result within graph theory and commutative algebra when their definitions and hypotheses are retained.[2] A claim that an arbitrary product of well-covered graphs is well-covered, or that a result extends to unrelated optimization systems, needs its own proof. The name alone provides no such transfer.
Examples¶
Canonical: the four-vertex path P4¶
Take vertices 1, 2, 3, 4 and edges 12, 23, 34. Hartnell presents P4 as well-covered and states that its maximal independent sets have size two.[1] Direct finite inspection gives exactly {1,3}, {1,4}, and {2,4}. No independent triple exists, and no listed pair admits another vertex.
Mapped back: The path and its three edges supply the declared finite graph. Nonadjacent pairs supply the relevant independent subsets. The three listed pairs pass inclusion-maximality. Their common size two supplies equal size across all maximal sets. The complete list is our check of Hartnell's named example, not a quotation of a printed enumeration.
Applied: the seven-vertex cycle C7¶
Take vertices 1 through 7 with edges between consecutive numbers modulo seven. Hartnell presents C7 as well-covered with maximal independent-set size three.[1] Exhaustive finite checking gives seven maximal independent sets, all of size three; every independent pair can be extended, while a cyclic independent set cannot have more than three vertices.
Mapped back: Cyclic adjacency supplies the declared finite graph. Sets without neighboring cycle vertices supply independent subsets. The seven unextendible triples pass inclusion-maximality. Their common size three supplies equal size across all maximal sets. This odd cycle has no leaves and differs from the path example even though the same condition holds.
Structural Tensions¶
No two-sided structural tension is established by the cited sources for this entry. Maximal versus maximum is a definitional distinction; one local extension test versus universal comparison is a proof burden. Treating either as a tradeoff to optimize would obscure the class condition. The useful diagnostic remains: has every maximal independent set been accounted for, or only one favorable outcome?
Structural–Framed Character¶
On the structural–framed spectrum, well-coveredness is strongly structural within graph theory: it is fixed by a finite adjacency relation and a universal quantifier over independent sets, not by an observer's preference. Evaluative weight: “well” is a historical label, not a claim that a graph is better for every task. Human practice: proving or using the property depends on mathematical choices of graph model and proof, but the truth of the condition for a declared graph does not depend on a particular analyst's judgment. Institutional origin: graph-theory literature names and studies the class; a historical attribution is separate from the defining test.[1]
Vocabulary travel: “independent” and “covered” have meanings outside graph theory, but the graph identity requires vertices, adjacency, maximality and cardinality. Import versus recognition: one must recognize those graph-theoretic roles before importing a broader claim about invariant outcomes. Its character: a formal graph class whose definition is exact and reusable across finite simple graphs, with no demonstrated substrate-neutral identity.
Structural Core vs. Domain Accent¶
Demonstrated core here. A declared graph carrier, its independent subsets, inclusion-maximality, and equal cardinality across every maximal subset recur in P4 and C7. Remove adjacency or the universal all-maximal-set condition and the named class disappears.
Domain accent. Path endpoints, the odd cycle, set labels and the values two or three belong to the examples. Even the name's historical origin is not constitutive. The graph-specific condition remains essential; substituting generic “all choices give the same result” loses independent-set feasibility and maximality.
Prime boundary. A future Prime about order-independent outcomes would need unlike documented non-graph settings with their own full role maps and a live-catalog identity check. These two graphs only establish transfer inside graph theory. No existing Prime parent is asserted from the word “invariance” alone.
Instantiates / Related Primes¶
Maximal Independent Set names a set that passes the unextendibility test. Well-covered Graph names a graph that passes a universal size test over all such sets. Graph Invariant concerns an assignment unchanged under graph isomorphism; a graph-class condition is not automatically that assignment identity. Well-colored Graph instead compares greedy coloring results over vertex orders. Generic Invariance vocabulary overlaps with equality across choices, but the full necessary roles of a strict parent require a separate graph test.
These are conceptual neighbors, not a DAG declaration. The path and cycle evidence grounds the entry's own graph-class identity without proving a strict edge to any neighbor.
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
Not to Be Confused With¶
- One maximum independent set: a graph may have one while another maximal set is smaller, as P3 shows.
- A maximal independent set: this is an individual vertex subset, not the all-sets condition on its graph.
- Well-colored graph: its all-order quantifier ranges over greedy vertex colorings, not maximal independent sets.
- Very-well-covered graph: the cited stronger category includes additional conditions such as no isolated vertices; those are not ordinary well-coveredness requirements.[2]
- A universal guarantee about greedy algorithms: extending an independent set until maximal produces a maximum set on a well-covered graph, but this does not certify unrelated heuristics or performance bounds.
References¶
[1] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i
[2] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j