Informatyka MIMUW

Zadanie 1
Wierzchołki grafu permutacji $G_n$ są etykietowane permutacjami zbioru $n$-elementowego. Dwa wierzchołki w tym grafie są połączone krawędzią, jeśli odpowiadające im permutacje różnią się transpozycją sąsiednich elementów. Dla jakich $n$ graf $G_n$ jest planarny?

Zadanie 2
Pokaż nieplanarność grafu Petersena
(a) z tw. Kuratowskiego (zawiera podgraf homeomorf. z K_3,3 lub K₅);
(b) wyprowadzając ograniczenie górne na liczbę krawędzi dla grafów planarnych o obwodzie r.

Zadanie 3