独立集

如果两个集合 和 的交集 为 （空集）时，则称它们是独立的。例如， 和 是独立的，但 和 不是独立的。独立集也称为不相交集或互斥集。

图 的独立顶点集是顶点的子集，使得子集中没有两个顶点代表 的边。上图显示了由若干图的两个子集组成的独立顶点集（轮图 、效用图 、彼得森图和 Frucht 图）。

独立边集也可以类似地定义 (Skiena 1990, p. 219)。

极大独立集是一个独立的集合，它是一个极大集，即不是任何其他独立集的子集的独立集。