\input dmmac

\serie8


\task
Graf $G$ nazveme {\I $k$-regul�rn�,} pokud stupe� ka�d�ho jeho vrcholu je roven $k$.
\subtask
Je pravda, �e ka�d� dva $(n-1)$-regul�rn� grafy jsou izomorfn�?
\body1
\subtask
Je pravda, �e ka�d� dva $(n-2)$-regul�rn� grafy jsou izomorfn�?
\body2

\task
Pro kter� $n$ existuje graf $G$ na $n$ vrcholech, jeho� stupn� jsou v�echny r�zn� a� na dva
(kter� tedy mohou b�t stejn�)? Pokud pro dan� po�et vrchol� $n$ graf existuje, popi�te jeho
konstrukci (�i jinak doka�te jeho existenci), pokud neexistuje, doka�te.
\body4


\task
Rozhodn�te, zda existuje nebo neexistuje nesouvisl� graf, jeho� dopln�k je op�t nesouvisl� graf.
To, co tvrd�te, pochopiteln� doka�te.
(Graf je souvisl�, pokud v n�m existuje cesta z ka�d�ho vrcholu do ka�d�ho.)
\body3

\task
Nech� $G=(V,E)$ je graf. Bijekci $f\:V\to V$ nazveme {\it automorfismus},
pokud plat� $\{u,v\}\in E \iff \{f(u), f(v)\}\in E$. (Je to tedy
izomorfismus grafu sama na sebe.)
Graf, kter� ma pouze jeden automorfismus (v�imn�te si, �e to bude identita)
nazveme {\it strnul�.}
Najd�te p��klad n�jak�ho strnul�ho grafu na $n>1$ vrcholech a doka�te to o n�m.
\body3


\bye

