A maximal independent vertex set of a graph is an independent vertex set that cannot be expanded to another independent vertex set by addition of any vertex in the graph.
A maximal independent vertex set of a graph 
is equivalent to a maximal clique
on the graph complement 
.
Note that a maximal independent vertex set is not equivalent to a maximum independent vertex set, which is an independent vertex set containing the largest possible number of vertices among all independent vertex sets. A maximum independent vertex set is always maximal, but the converse does not hold.
A subset 
of the vertex set 
of a graph is a maximally independent vertex set iff 
is both a dominating set and an independent
vertex set (Burger et al. 1997).
Any maximal independent vertex set is also both minimal dominating and maximal irredundant (Mynhardt and Roux 2022). As a result, the lower independence number (which is the size of a smallest maximal independent vertex set) is equivalent to the independent domination number.
Fairfax-Ball (2026) proved that choosing a uniformly random ordering of the vertices of a finite nonempty tree and greedily including each graph vertex with no previously included adjacent
vertex gives a uniform distribution on its maximal independent vertex sets iff the tree is the one-vertex complete graph 
or the single-edge complete
graph 
. Fairfax-Ball (2026) reports ChatGPT assistance with
the Lean formalization.
A maximal independent vertex set of a graph can be computed in the Wolfram Language using FindIndependentVertexSet[g, Infinity], and all maximal independent vertex sets can be computed using FindIndependentVertexSet[g, Infinity, All].
