Graf pusty to graf bez krawędzi. Antyklika lub graf niezależny to inne nazwy grafu pustego. Antyklikę o \( n \) wierzchołkach oznaczać będziemy przez \( \mathcal{A}_{n} \).
Graf pełny to graf, w którym każde dwa wierzchołki połączone są krawędzią. Graf pełny nazywany jest także kliką i oznaczany przez \( \mathcal{K}_{n} \), gdzie \( n \) jest liczbą jego wierzchołków.
Uwaga
Liczba krawędzi w klice \( \mathcal{K}_{n} \) wynosi \( \frac{n(n-1)}{2} \).
Graf dwudzielny to graf \( \mathbf{G}=( V,E ) \), w którym zbiór \( V \) da się podzielić na dwa rozłączne podzbiory \( V_1 \) oraz \( V_2 \) tak, by żadne dwa wierzchołki w obrębie tego samego podzbioru \( V_i \) nie były sąsiadami. Czasem, dla podkreślenia takiego podziału, graf dwudzielny będziemy oznaczać przez \( ( V_1\cup V_2,E ) \). Zauważmy jednak, że podział taki nie jest jednoznaczny -- np. w antyklice \( \mathcal{A}_{n} \) dowolny podział zbioru wierzchołków na dwa podzbiory jest podziałem dwudzielnym.
Pełny graf dwudzielny to graf dwudzielny \( \mathbf{G}=( V_1\cup V_2,E ) \), w którym każdy wierzchołek z \( V_1 \) jest połączony z każdym wierzchołkiem z \( V_2 \). Pełny graf dwudzielny oznaczać będziemy przez \( \mathcal{K}_{r,s} \), gdzie \( r \) jest rozmiarem \( V_1 \), a \( s \) rozmiarem \( V_2 \).
Graf płaski to para \( \mathbf{\overline{G}}=( \overline{V},\overline{E} ) \), gdzie:
Graf planarny to graf, który jest prezentowalny jako graf płaski.