Spójnością grafu lub spójnością wierzchołkową grafu nazywamy taką liczbę $k$, że usunięcie z grafu pewnych $k$ wierzchołków spowoduje, że graf przestanie być spójny lub zredukuje go do jednego wierzchołka, ale usunięcie dowolnych $k-1$ wierzchołków zawsze pozostawi graf spójny.
(Wierzchołki usuwamy wraz z dochodzącymi do nich krawędziami.)

Spójność grafu $G$ oznaczamy $\kappa(G)$.

??? Czy istnieje graf 3-regularny o spójności 1?

Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej