O subgraph conectate de un grafic care nici un nod poate fi adăugată şi încă mai fi conectat. Formale, definirea: dat un grafic G = (V, E), o subgraph S = (V', E ") este o componentă maxim conectate dacă

• S este conectat, şi
• pentru toate nodurile u astfel că u∈ V şi tu ∉ V' nu există nici o v∈ de noduri V' pentru care (u, v) ∈ E.