1. Ile krawedzi trzeba dolozyc do K_{3,3}, zeby byl eulerowski? 2. Z kompletu domina usuwamy 0-1, 0-2, 0-3. Ile jeszcze trzeb ausunac, zeby dalo sie ulozyc reszte w lancuch zamkniety? 3. Ktore pelne grafy 2- i 3-dzielne sa eulerowskie? Hamiltonowskie? 4. Pok., ze dla dow. spojnego grafu G graf G^3 jest hamilt., a G^2 niekoniecznie, gdzie w G^k krawedzie lacza te wierzch., miedzy ktorymi w G jest sciezka nie dluzsza niz k. 5. Pokaz, ze w turnieju silnie spojnym sa cykle wszystkich dlugosci (Wilson). 6. Pokaz, ze graf Petersena jest nieplanarny (a) wskazujac podgraf homeomorf. z K_{3,3} lub K_5 (b) uogolniajac oszacowanie m<=3n-6 na grafy o obwodzie r. 7. Dla jakich k hiperkostka Q_k jest planarna? Dla jakich r,s,t pelny graf trojdzielny K_{r,s,t} jest planarny? 8. Pok., ze jesli G ma >= 11 wierzch., to G lub G' (dopelnienie) jest nieplanarny. Podac przyklad, ze dla 8 wierzch. tak nie musi byc. 9. Ile max. krawedzi moze miec graf zewn. planarny? Pok., ze taki graf mozna pokolorowac 3 kolorami. 10.* Ud. 'tw. o 7 barwach' dla grafow na torusie (Wilson). 11.* Graf Knesera K(r,n): V = r-podzbiory {1..n} (A,B) jest krawedzia witw A i B maja niepuste przeciecie. Pok, ze K(2,5) ( = graf Petersena) ma l. chromat. 3, K(2,6) ma l.chr. 4, ogolnie K(r,n) ma l. chr. <= n-2r+2 12.* Graf Mycielskiego M_n: M_2 = jedna krawedz; M_{k+1}: do M_k dokladamy kopie M' samych wierzch. M_k Kazdy wierzch. w M' jest polaczony ze wszystkimi sasiadami _swojego odpowiednika_ w M_k. Dokladamy jeszcze nowy wierzch. v, polaczony ze wszystkimi wierzch. w M'. Ud., ze: (a) w M_k nie ma trojkatow (b) liczba chromat. M_k = k 13. Znalezc wiel. chromat. cyklu n-wierzch. i 'kola o n szprychach'.