\input dmmac

\serie9


\task
Rozhodn�te (a va�e tvrzen� doka�te) pro ka�dou kombinaci ��sel $n,k\in\N$,
zda existuje �i neexistuje $k$-regul�rn� graf na $n$ vrcholech.
\body5

\task
Doka�te, �e ka�d� graf $G$ m� {\I skorovyv�enou orientaci.}
To znamen�, �e ka�dou hranu $e\in E(G)$ zorientujeme tak, �e ve v�sledku
se pro ka�d� vrchol $v\in V(G)$ v�stupn� stupe� $\deg^-_G(v)$ (tedy
po�et hran co z $v$ vych�z�) li�� od vstupn�ho stupn� $\deg^+_G(v)$
(po�et hran co do $v$ vch�z�) nejv��e o jedna.
\body4


\task
Nech� $T$ je strom.
Doka�te, �e $T$ m� aspo� $\Delta(T)$ list�.
(Symbol $\Delta(G)$ zna�� maxim�ln� stupe� grafu $G$.)
\body3


\task
Doka�te, �e v ka�d�m grafu $G$ existuje cesta d�lky $\delta(G)$.
(Symbol $\delta(G)$ zna�� minim�ln� stupe� grafu $G$.)
\body2

\task
Doka�te, �e v ka�d�m grafu $G$ s $\delta(G)\ge2$ existuje kru�nice d�lky
alespo� $\delta(G)+1$.
\body3

\task
Nech� $n\in\N, n\ge2$. Doka�te, �e posloupnost cel�ch ��sel $(d_1,d_2,\dots,d_n)$ je sk�re n�jak�ho stromu,
pr�v� tehdy kdy� $d_i>0$ pro $i=1,\dots,n$ a plat� $\sum_{i=1}^n d_i = 2(n-1)$.
\body4

\task
Doka�te, �e pro barevnost libovoln�ho grafu $G$ plat�
$$
\chi(G) \le \Delta(G)+1.
$$
\body3


\task
Devaten�ct rodin si navz�jem pos�l� novoro�n� p��n�,
ka�d� rodina jich roze�le dev�t ostatn�m (r�zn�m) rodin�m.
Doka�te, �e existuje rodina, kter� dostala p��n� od rodiny,
kter� sama nep��la.
\body3

\task
Nech� $G$ je rovinn� graf, jeho� v�echny stupn� jsou alespo� 5.
Doka�te, �e $G$ nutn� mus� m�t alespo� 12 vrchol�.
\body3



\bye

