Ušaté lemma

1. Nechť $G$ je graf s aspoň třemi vrcholy. Dokažte, že $G$ je 2-souvislý, právě když pro každé tři různé vrcholy $x, y, z$ existuje v $G$ cesta z $x$ do $y$ obsahující $z$.
2. Nechť $G$ je graf s aspoň třemi vrcholy. Dokažte, že $G$ je 2-souvislý, právě když pro každé tři různé vrcholy $x, y, z$ existuje v $G$ cesta z $x$ do $y$ neobsahující $z$.

Počítání dvěma způsoby

1. Na vysoké škole si každý student zapsal aspoň $10\%$ ze všech nabízených předmětů. Dokažte, že existuje předmět, na němž je zapsáno aspoň $10\%$ všech studentů.
2. Z přednášky víme, že na vrcholech $\{1, 2, \dots , n\}$ existuje $n^{n-2}$ stromů. Kolik z nich obsahuje hranu $\{1, 2\}$?
3. Na turnaji v trojkovém mariáši (což je hra pro tři hráče) bylo $32$ účastníků, $12$ z nich sehrálo pět partií, $20$ z nich sehrálo šest partií. Kolik tam bylo sehráno partií?
4. Na jiném turnaji v trojkovém mariáši bylo $15$ účastníků a každá dvojice účastníků se tam právě dvakrát sešla u společné partie. Kolik tam bylo sehráno partií? Plyne ze zadání, že každý hráč sehrál stejný počet partií? Pokud ano, kolik partií sehrál každý hráč?
5. Turistický oddíl má $100$ členů. Pro své členy oddíl zorganizoval celkem $10$ výletů. Na každém výletě bylo nejvýše $30$ členů oddílu. Dokažte, že existují dva členové oddílu, kteří spolu nikdy nebyli na společném výletě.
6. Nechť $M$ je matice tvaru $10\times 10$ obsahující čísla $1, 2, \dots , 10$, přičemž každé číslo se v ní vyskytuje $10$-krát. Dokažte, že $M$ má řádek nebo sloupec obsahující aspoň 4 různá čísla. Jak zobecnit tento závěr na matice tvaru $n\times n$, v nichž se každé z čísel $1, 2, \dots , n$ vyskytuje právě $n$-krát?

Nekonečné vs. libovolně velké

1. Ukažte, že existuje nekonečný graf $G$, který pro každé $k\in \N$ obsahuje cestu délky $k$, ale neobsahuje nekonečně dlouhou cestu.
2. Ukažte, že existuje posloupnost $a$ reálných čísel taková, že pro každé $k\in\N$ v ní existuje rostoucí podposloupnost (ne nutně souvislá) délky $k$, ale neexistuje v ní nekonečná rostoucí podposloupnost.

Ramseyovské problémy

Rozhodněte, která z následujících tvrzení jsou pravdivá ($K_N$ značí úplný graf na množině vrcholů $\{0,1,\dots, N-1\}$):

1. Pro každé dostatečně velké $N \in \N$ platí, že když hrany $K_N$ obarvíme dvěma barvami, pak vždy bude existovat jednobarevný úplný podgraf na deseti vrcholech, který obsahuje vrchol číslo 0.
2. Pro každé dostatečně velké $N \in \N$ platí, že když hrany $K_N$ obarvíme dvěma barvami, pak vždy bude existovat jednobarevný úplný podgraf na deseti vrcholech, jehož každý vrchol je mocnina dvojky.
3. Trojbarevná verze: $\forall k,l,m \in \N: \exists N\in \N:$ $\forall$ obarvení hran $K_N$ červeně/modře/zeleně: $G$ obsahuje červený indukovaný podgraf na $k$ nebo modý na $l$ nebo zelený na $m$ vrcholech.
4. Vícebarevná: $\forall c, k \in \N: \exists N\in \N:$ $\forall$ obarvení $c$ barvami hran grafu $K_N$: $G$ obsahuje jednobarevný indukovaný podgraf na $k$ vrcholech.