\input dmmac

\serie{10}


\task
Doka�te, �e �pln� bipartitn� graf $K_{n,m}$ je rovinn� pr�v� tehdy,
kdy�
$$\min\{n,m\}\le 2.$$
\body3

\task
Doka�te, �e barevnost rovinn�ch graf� bez troj�heln�ku je 4,
a to bez pomoci v�ty o �ty�ech barv�ch.
Hint: doka�te, �e ka�d� takov� graf je 3-degenerovan�.
\body6

\task
Nech� $G$ je graf. Doka�te n�sleduj�c� vztah:
$$
\chi(G)\cdot\alpha(G) \ge |V(G)|,
$$
kde $\chi(G)$ zna�� chromatick� ��slo a $\alpha(G)$ velikost
nejv�t�� nez�visl� mno�iny v $G$.
\body5


\task
Precizn� doka�te, �e graf je rovinn�, pr�v� kdy� ka�d� jeho d�len� je rovinn�.
\body2

\task
Kolik koster m� �pln� bipartitn� graf $K_{2,n}$?
\body4

\task
Nech� $G$ je souvisl� graf.
Doka�te, �e pro ka�dou hranu $e\in E(G)$ existuje kostra $K$ grafu $G$,
kter� hranu $e$ obsahuje.
\body4

\bye

