Graf spójny – graf, w którym z wyznaczonego wierzchołka V możliwe jest przejście do dowolnego innego wierzchołka za pomocą ścieżki. Graf nieposiadający powyższej własności to graf niespójny.
Graf spójny – graf, w którym każdą parę wierzchołków łączy pewna ścieżka. Graf nieposiadający powyższej własności to graf niespójny.
Warunkiem koniecznym, by graf skierowany był spójny, jest spójność jego grafu podstawowego (tego samego grafu bez kierunków na krawędziach).
Spójne składowe Maksymalny, w sensie inkluzji, spójny podgraf grafu nazywa się spójną składową. Liczba spójnych składowych grafu G oznacza się przez
Inaczej, spójną składową grafu G jest jego spójny podgraf nie zawarty w większym podgrafie spójnym grafu G.
Nieformalnie, spójna składowa grafu jest to taki podgraf, który można ‘wydzielić’ z całego grafu bez usuwania krawędzi. Graf spójny ma jedną spójna składową. Dla przykładu, w lesie spójnymi składowymi są drzewa. Spójna składowa to fragment grafu, który nie jest połączony z innym fragmentem.
oznacza, że graf G jest spójny, oznacza, że G składa się z izolowanych wierzchołków.