Numărul de independență al unui grafic este dimensiunea celui mai mare set independent de vârfuri din acesta.
Deoarece problema mulțimii independente este NP-completă , nu există algoritmi cunoscuți pentru determinarea numărului de independență într-un grafic arbitrar care să funcționeze în timp polinomial.
În orice grafic , numărul de independență este legat de numărul de acoperire a vârfurilor prin prima identitate Gallai : , în plus, complementul celui mai mare set de vârfuri independent este cel mai mic acoperire de vârf. Folosind acest fapt, într-un graf bipartit poate fi găsit în timp polinomial, deoarece problema celui mai mic vârf de acoperire din acesta se reduce la găsirea celei mai mari potriviri .
Într-un grafic fără vârfuri izolate (vârfurile de gradul 0), inegalitatea este valabilă și , unde este numărul de acoperire a muchiei graficului . Într -un graf bipartit fără vârfuri izolate, datorită Teoremei lui König , .