A független ponthalmaz precíz definíciójára mindjárt kettő is van.
Íme az egyik:
Egy $G$ gráfban független csúcshalmaznak nevezzük a csúcsoknak az $A \subset V(G)$ részhalmazát, ha nincs olyan él, amelynek mindkét végpontja $A$-ban van.
És itt jön a másik:
Egy $G$ gráfban független csúcshalmaznak nevezzük a csúcsoknak az $A \subset V(G)$ részhalmazát, ha az $A$ által feszített részgráf nem tartalmaz élt.
Egy $G$ gráfban a független csúcsok maximális számát $\alpha(G)$-vel jelöljük.
