JTM VI, Etap IIIB

(\(1+2^{-6}\) punktu)Zdefiniujmy następujące grafy:

• \(F_1\) --- graf pełny \(K_4\),
• \(F_2\) --- graf pełny \(K_5\),
• \(F_3\) --- graf pełny dwudzielny \(K_{2,10}\),
• \(F_4\) --- graf pełny dwudzielny \(K_{3,3}\),
• \(F_5\) --- cykl \(C_{5}\),
• \(F_6\) --- cykl \(C_{6}\).

Dla każdego \(i \in \{1,2,\ldots,6\}\) niech \(G_i\) będzie grafem na \(1000\) wierzchołkach, który ma maksymalną możliwą liczbę krawędzi i nie zawiera grafu \(F_i\) jako podgrafu. Wypisz grafy \(G_1, G_2, \ldots, G_6\) w kolejności od tego, który ma najmniej krawędzi do tego, który ma najwięcej krawędzi.

(\(1+2^{-5}\) punktu)Ile maksymalnie krawędzi może mieć graf na \(21\) wierzchołkach, który nie zawiera ścieżki składającej się z \(8\) wierzchołków?

(\(1+2^{-4}\) punktu)Jaka jest największa możliwa liczba krawędzi w grafie na \(2023\) wierzchołkach niezawierającym żadnego cyklu?

(\(1+2^{-3}\) punktu)W Jagiellońskim Turnieju Szachowym wzięło udział \(36\) osób, które rozegrały ze sobą \(80\) partii. Żadna para nie grała ze sobą dwukrotnie. Ula zauważyła, że istnieje grupa \(a\) osób, które nie grały w ogóle między sobą. Jaka jest największa możliwa liczba~\(a\), dla której Ula zawsze mogła znaleźć taką grupę?

(\(1+2^{-2}\) punktu)Jaka jest największa możliwa liczba krawędzi w grafie na \(36\) wierzchołkach niezawierającym podgrafu \(F\) utworzonego z grafu pełnego \(K_{11}\) przez usunięcie krawędzi cyklu na \(5\) wierzchołkach?

(\(1+2^{-1}\) punktu)Jaka jest największa taka liczba \(a\), że wśród \(30\) punktów w kole o promieniu~\(1\) musi być co najmniej \(a\) par punktów w odległości co najwyżej \(\sqrt{2}\)?