Független ponthalmaz

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.