\input dmmac

\serie{10}

\task
Nech� $G$ je rovinn� vrcholov� 2-souvisl� graf a uva�me libovoln� jeho rovinn� nakreslen�.
Po��dn� doka�te, �e hranice ka�d� st�ny (i t� vn�j��) je grafov� kru�nice.
\body3

\task
Doka�te, �e ve vrcholov� 2-souvisl�m grafu pro ka�d� dv� hrany existuje kru�nice, kter� je obsahuje. 
\body4

\task
Existuje hranov� 2-souvisl� graf, kde n�jak� dv� jeho hrany nele�� na kru�nici?
\body3

\task
Doka�te �i vyvra�te: Pro ka�d� $n\in\N$ existuje $N\in\N$,
�e jsou-li hrany �pln�ho grafu $K_N$ libovoln� obarveny $n$ barvami,
potom v uva�ovan�m $K_N$ existuje �pln� podgraf $K_n$, jeho� v�echny
hrany maj� tut� barvu.
\body3

\task
Doka�te �i vyvra�te: Pro v�echna $n,p\in\N$ existuje $N\in\N$, �e je-li
$X$ libovoln� $N$-prvkov� mno�ina, jej�� ka�d� nepr�zdn� podmno�ina
velikosti nanejv�� $p$ je obarvena jednou ze dvou barev,
potom existuje $n$-prvkov� podmno�ina $Y\subseteq X$,
jej�� v�echny podmno�iny velikosti nejv�� $p$ maj� tut� barvu.
\body3

\task
Doka�te, �e pro ka�d� $k\in\N$ existuje $N\in\N$ takov�, �e
libovoln� $N$-prvkov� posloupnost re�ln�ch ��sel obsahuje neklesaj�c�
nebo nerostouc� podposloupnost d�lky $k$.
\body5


\bye

