Independent Set
Two sets 
and 
are said to be
independent if their intersection 
,
where 
is the empty
set. For example, 
and 
are independent,
but 
and 
are not.
Independent sets are also called disjoint or mutually
exclusive.
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 
. The figure above
shows independent vertex sets consisting
of two subsets for a number of graphs (the wheel graph 
, utility graph 
, Petersen graph,
and Frucht graph).
An independent edge set can be defined similarly (Skiena 1990, p. 219).
Contact the MathWorld Team
graph properties