An independent vertex set of a graph is a subset of the vertices such that no two vertices in the
subset represent an edge of . Given a vertex cover of a
graph, all vertices not in the cover define a independent
vertex set (Skiena 1990, p. 218). A maximum independent vertex set is an independent
vertex set containing the largest possible number of vertices for a given graph.

A maximum independent vertex set is not equivalent to a maximal independent vertex set, which is simply an independent vertex set that cannot
be extended to a larger independent vertex set. Every maximum independent vertex
set is also an independent vertex set, but
the converse is not true.

The independence number of a graph is the
cardinality of the maximum independent set.

Maximum independent vertex sets correspond to the complements of minimum
vertex covers.