Spójnością krawędziową grafu nazywamy taką liczbę $k$, że usunięcie z grafu pewnych $k$ krawędzi spowoduje, że graf przestanie być spójny, ale usunięcie dowolnych $k-1$ krawędzi zawsze pozostawi graf spójny.
(Krawędzie usuwamy bez wierzchołków do których dochodzą.)

Spójność krawędziową grafu $G$ oznaczamy $\kappa'(G)$.

Można pokazać, że zachodzi zależność:

$\kappa(G)$ $\leq$ $\kappa'(G)$ $\leq$ $\delta(G)$.

???
Czy istnieje graf o $\delta(G)$ $= 3,$ $\kappa'(G)$ $= 2$ i $\kappa(G)$ $= 1$?

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