Rdzeń grafu

Rdzeń grafu to graf powstały przez kolejne usuwanie z grafu wierzchołków stopnia pierwszego, aż do momentu, gdy takich wierzchołków w grafie nie będzie. Przy tym zawsze wraz z wierzchołkiem v usuwamy krawędź, która ma v za swój wierzchołek.

Z dowolnej acyklicznej komponenty grafu ostanie się w rdzeniu tylko jeden (dowolny) wierzchołek. Z pozostałych komponent do rdzenia wejdą te i tylko te wierzchołki i krawędzie, które należą do cykli.

Na każdym kroku istnieje na ogół wybór więcej niż jednego wierzchołka + krawędzi do usunięcia, ale ostateczny wynik, rdzeń, niemalże jest niezależny od tych wyborów (co wynika z ostatniej uwagi powyżej), a klasa izomorficzna rdzenia jest po prostu niezależna od wspomnianych wyborów, a zależy jedynie od klasy samego grafu. Przy tym dodatkowo mamy identycznościowe zanurzenie rdzenia w danym grafie.