獨立集

如果兩個集合 和 的交集 為 （空集）時，則稱它們是獨立的。例如， 和 是獨立的，但 和 不是獨立的。獨立集也稱為不相交集或互斥集。

圖 的獨立頂點集是頂點的子集，使得子集中沒有兩個頂點代表 的邊。上圖顯示了由若干圖的兩個子集組成的獨立頂點集（輪圖 、效用圖 、彼得森圖和 Frucht 圖）。

獨立邊集也可以類似地定義 (Skiena 1990, p. 219)。

極大獨立集是一個獨立的集合，它是一個極大集，即不是任何其他獨立集的子集的獨立集。