Maximum Independent Vertex Set

An independent vertex set of a graph G is a subset of the vertices such that no two vertices in the subset represent an edge of G. 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.


A maximum independent vertex set in a given graph g can be found in the Wolfram Language using FindIndependentVertexSet[g][[1]]. The command Sort[FindIndependentVertexSet[g, Length /@ FindIndependentVertexSet[g], All]] will find all maximum independent vertex sets.

See also

Independence Number, Independent Set, Independent Vertex Set, Maximal Independent Vertex Set, Maximum Independent Edge Set, Maximum Independent Set Problem, Minimum Vertex Cover, Vertex Cover

Explore with Wolfram|Alpha


Myrvold, W. and Fowler, P. W. "Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85, 173-194, 2013.Pemmaraju, S. and Skiena, S. "Maximum Independent Set." §7.5.3 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 318, 2003.Skiena, S. "Maximum Independent Set." §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.

Cite this as:

Weisstein, Eric W. "Maximum Independent Vertex Set." From MathWorld--A Wolfram Web Resource.

Subject classifications