1. nahodne grafy
2. prieskum grafov
3. mame kubicky graf hranovo zafarbeny 3 farbami. Nech S je hranovy
   rez |S|=n. ozn. n_i = pocet hran S_n zafarbenych farbou i. Dokazte,
   ze n_1 \equiv n_2 \equiv n_3 \equiv n (mod 2) 

1. Eulerovske grafy a algoritmus na hladanie eulerovskeho tahu
2. Planarne grafy (Kuratowski)
3. Dokazte: Ak rad(G) \geq 3, tak rad(\bar{G}) < 3
   Este sa ma spytal ci viem rychlo ukazat, ze Petersen nie je hamiltonovsky.

1. Toky
2. Hranove farbenia
3. Nejaky priklad s blokovymi grafmi

1. Toky v sietach
2. Hamiltonovske grafy
3. Ukazat ze v kubickom grafe hranova=vrcholova (suvislost)

1. Tutteho veta o 1-faktore v grafe kde platia tie srandy o neparnych
   komponentoch. Vyuzitie Tutteho vety pri dokaze nasledujucej Petersenovej
   teoremy o kubickych bezmostych grafoch.
2. Hamiltonovske grafy. Teda Diracova podmienka, Chvatal a nejake kecy
   okolo HAM kruznic v 4-suvislych grafoch.
3. Samokomplementarne grafy a veticka o tom, ze |V(G)| je kongruentne s
   0, alebo 1 podla modulo 4. Nejake priklady na samokomplementarne grafy 
   a princip ako sa taketo grafy konstruju.
4. Algoritmus hladania najvacsieho parenia v bipartitnom grafe.  Chcel
   dve verzie. Jedna je ta co hlada najdlhsiu alternujucu cestu (pripadne
   iteruje predlzujuce cesty) a druha je o vyuziti tokov na najdenie 
   takehoto parenia.

1. k-toky pre male k
2. Nahodne grafy
3. Nech G ma chromaticke cislo \geq k, potom obsahuje aspon k vrcholov stupna 
   aspon k-1

1. Hranove farbenia+dokazat nejaka zlozitejsia veta (Konig napr)
2. Priestory cyklof (vsetko o tom, veta Kirchhoff)
3. Dok, ze v kubickom grafe exist. kostra T taka, ze G-E(T) je acyklicky

1. extermalne problemy+Turan
2. Chromaticky polynom
3. nieco cosi

1. TUTTEho veta o 1-faktore (ze vraj to dava len ludom, ktorych nema rad)
2. EULEROVSKE grafy + alg. najdenia tahu
3. PRIKLAD z domacej ulohy

1. Mengerova teorema.
2. Prieskum labyrintov (Tarry a pod.)
3. Chromaticky index kompletnych grafov.

1. Existencia 1-faktorov v grafoch.
2. Celociselne toky a toky na grupach.
3. Ak mame v bipartitnom grafe dve max. parenia vzhladom na inkluziu,
   tak maju rovnaky pocet hran. Dokazte.

1. hranove farbenia (Vizing)
2. k-toky (k-tok \iff Z_k-tok)
3. kazdy G ma cestu dlzky \delta(G) a kruznicu dlzky \delta(G)+1
   priklad grafu, ktory nema 4-tok ale ma 5-tok

1 Toky v sietiach (veta, algoritmus)
2 Chromaticky polynom 
3 Ak chromaticke cislo grafu G \geq k, tak potom v G existuje aspon k
  vrcholov so stupnom \geq k-1

1. Kuratovskeho teorema
2. Prehladavanie grafov
3. ak G je samokomplementarny tak je suvisly a diam(G) \leq 3

1. Pravdepodobnostne metody v grafoch
2. Algoritmus na hladanie eulerovskeho tahu
3. Ak G je hamiltonovsky alebo eulerovsky, tak jeho hranovy graf je
   hamiltonovsky

1. extremalne problemy (aj tie limity)
2. dualny graf, vlastnosti, pouzitie
3. blokovo artikulacny graf suv. grafu je strom

1. Existencia 1 faktora v grafoch (tutte, peterson, tie dosledky hall.
   podmienky pre k suvisle grafy)
2. Cyklovy priestor (def. + kirchhoff)
3. Ak je G k-kriticky, tak pre kazde u,v \in V(G) musi platit:
   N(v) nie je podmnozinou N(u) a naopak (N(v) - mnozina susedov v)

1. Greedy algoritmus pre farbenie grafov a horny odhad chromatickeho
   cisla (ak viete, tak aj Brooksovu vetu)
2. Nahodne grafy (daval nechutne teoreticke otazky z prednasok)
3. Pre kazdy strom T plati:
   T ma 1-faktor \iff pre kazdy v z V plati q(T-v)=1

1. Toky v sietach
2. Mengerova teorema
3. Dokazte, ze strom ma najviac jeden 1-faktor.

1. Bipartitne parenia
2. Veta o zafarbeni planarneho grafu 5 farbami
3. Ak mame 2-suvisly graf, tak dokazte, ze bod a hrana, ktora neobsahuje
   dany bod, lezia na kruznici. 

1. Eulerov polyedralny vzorec a jeho dosledky
2. Brooks
3. G je K regularny graf a neparnym poctom vrcholov N. Potom Chi'(G)=K. 

1. Mengerova veta
2. Nikde nulove toky na grafoch (malo to nejaku suvislost s k-tokmi)
3. Dokazat, ze strom ma najviac jeden 1-faktor.

1. chvatalova teorema o ham. grafoch
2. priestory cyklov
3. dokazte ze ziaden vrcholovy rez v k-kritickom grafe neindukuje kompletny
   podgraf. ( k-kriticky graf je graf s chrom. cislom k pri ktorom pri odobrati
   lub. vrchola znizime chrom. cislo a vrcholovy rez je mnozina vrcholov po
   ktorej odobrati sa graf rozpadne na komponenty )

1. Kuratowski
2. Konig o pareni
3.  rad(G) \leq diam(G) \leq 2 rad(G)

1. Farbenie hran - napisal som Koniga s dokazom a chcel este znenie Vizinga
2. Ford-Fulk. veta + dokaz (Mal som)
3. Nech G je graf v ktorom je hamiltonovska kruznica a S ja vlastna neprazdna 
   podmnozina V(G), tak c(G-S) \leq |S|+1, kde to c je pocet komponentov grafu.
   V poznamkach je jedna velmi podobna veta, dokaz sa robi rovnako, az na to,
   ze to +1 potrebujeme v baze indukcie. Toto som vedel na 80%

1. Vizing
2. Toky v grupach 
3. jednoznacne hranovo 3-zafarbitelny kubicky graf je hamiltonovsky

1. Hamiltonovske grafy
2. Farbenia planarnych grafov + Heawood
3. Ak je graf hamiltonovsky alebo eulerovsky, potom jeho hranovy graf
   je hamiltonovsky.

1. Eulerov polyedralny vzorec
2. Brooks
3. Ak G je d-regularny graf neparneho radu (pocet vrcholov G je neparny), 
   potom sa da hranovo zafarbit len d+1 farbami ( chi'(G) = d+1 ).

1. tutt. o 1-faktore
2. celocis. toky, toky na grupach, k-toky
3. priklad z cvik: dokazte, ze lubov. (vrchol.) rez k-kritic. grafu
   neindukuje kompletny podgraf
  
1. Menger + na konci sa ma este spytal na dosledok pre 2 vrcholy 
2. z planarnych grafov 
   - stereograficka projekcia + pouzitie
   - dualne grafy + pouzitie
3. Dokazat: 
   Pre kazdy strom T plati, ze Rad(T) = \lceil Diam(T)/2 \rceil
  
1. Toky v sietach.
2. Petersenova veta (Kazdy kubicky graf bez mostov ma 1 faktor)
3. Blokovy graf B_G  grafu G je strom.

1. Kuratowski
2. Existencia 1-faktorov, 2-f. a faktorizacii v reg. grafoch
3. chromaticky index v kompletnych grafoch (rada: zratajte K_{2k+1} a podla
   toho K_{2k})

1. Brooksova veta
2. Eulerova veta o planarnych grafoch + dosledky
3. Dokazat ze kazdy suvisly graf sa da rozdelit aspon na 2 dominantne podgrafy.

1. Farbenie planarnych grafov
2. toky na grupach a k-toky
3. Dokazte, ze kazdy uzavrety neparny sled obashuje kruznicu neparnej dlzky

1. 1-faktor 2-faktor
2. farbenie planarnych grafov
3. kubicky graf, existuje kostra T, ze G-E(T) je acyklicky

1. Parenie v bipartitnych grafoch
2. Ford-Fulkerson aj algoritmus
3. Ak G neobsahuje kruznicu parnej dlzky potom jeho bloky su tvaru
   K_1, K_2 alebo kruznica neparnej dlzky, teda C_{2k+1}

1. ako vzdy
2. ako vzdy
3. Dokazte, ze kazdy suvisly graf, ktory nie je blok, obsahuje aspon dva bloky,
   z ktorych kazdy ma len 1 artikulaciu.

1. Mengerova teorema
2. Chromaticky polynom
3. Dokazte, ze kazdy sled neparnej dlzky obsahuje neparnu kruznicu.