Czy istnieje graf skierowany Max: Czy istnieje graf nieskierowany o 7 wierzchołkach i 2 składowych spójnych, w którym stopnie wynoszą 4,2,4,2,4,2,2,? Uzasadnij.

Pytający: Nie istnieje. Weźmy wierzchołek o stopniu 4, ma on 4 wierzchołki sąsiadujące, a zatem składowa spójna, do której należy musi mieć co najmniej 5 wierzchołków. Łącznie mamy 7 wierzchołków, zatem druga składowa spójna może mieć 1 lub 2 wierzchołki. 1 wierzchołek odpada, gdyż mielibyśmy wierzchołek o stopniu 0. Zatem jedna ze składowych spójnych musi się składać z 2 wierzchołków połączonych krawędzią, są to wierzchołki o stopniach 2, 2. Pozostaje pytanie, czy da się utworzyć drugą składową spójną z wierzchołków o stopniach 2,2,4,4,4. Rozważmy graf pełny o 5 wierzchołkach. Wszystkie jego wierzchołki mają stopień 4, my zaś chcemy mieć 3 wierzchołki tego stopnia. Zatem nie możemy usunąć krawędzi z 3 wierzchołków, stąd możemy jedynie usunąć krawędź łączącą pozostałe 2 wierzchołki. Otrzymamy wtedy graf o wierzchołkach stopnia 3,3,4,4,4. Usunięcie jakiejkolwiek kolejnej krawędzi sprawi, iż nie będziemy mieli już 3 wierzchołków stopnia 4, zatem nie da się utworzyć takiej składowej spójnej.