Matematické Fórum

Dobrý den,
dostal jsem úkol dokázat, že všechny (n-2)-regulární grafy na n vrcholech jsou regulární.
Vypracoval jsem řešení a moje otázka je, jestli je toto řešení korektní nebo, jeslti musím brát v ohled nějaké jiné argumenty. Děkuji

Pokud jsou dva grafy isomorfní, jsou isomorfní i jejich doplňky. Stačí tedy dokázat, že jsou isomorfní doplňky (n-2)-regulárních grafů.
Doplňky (n-2) regulárních grafů na n vrcholech jsou 1-regulární grafy, protože úplný graf na n vrcholech je je (n-1)-regulární. Aby takový graf existoval, musí být n sudé, protože jeho 1-regulární grafy mají všechny stupně 1, takže ke každému bodu musí vést právě jedna hrana, hrana je tvořena právě dvěma body, tudíž počet vrcholů je roven |V(G)|=2|E(G)|. 1-regulární graf je vždycky isomorfní, protože kromě isomorfních variant neexistují žádné jiné 1-regulární grafy. Z toho vyplývá, že i (n-2)-regulární graf je isomorfní.