# Domácí úkol 6.3 - skup
Nejvyšší počet stupně v grafu je $n-1$. To znamená, že v $(n-2)$-regulárním grafu bude každý vrchol spojen se všemi vrcholy kromě jednoho.
Pro hledání isomorfismu můžeme využít doplňku grafu; zde má každý vrchol stupeň $1$, tzn. jedna hrana bude spojovat dva vrcholy.

(Toho nemůžeme dosáhnout pro lichý počet vrcholů (což nevadí, protože pro neexistující graf nemusíme otázku isomorfismu nijak řešit). Důvodem je pravidlo sudosti - pokud každý vrchol má lichý stupeň, musí jich být sudý počet.)

Grafy, kde má každý vrchol stupeň $1$, vždy budou isomorfní pro stejný počet vrcholů - elementy grafu lze např. umístit do řady tvořené opakovanými trojicemi *vrchol-hrana-vrchol*. Jsou-li isomorfní doplňky, pak budou isomorfní i původní grafy (dokázáno dříve).