1. Tekintse a G síkgráf ábrán látható szép lerajzolását.
a) Hány csúcsa, éle és tartománya van G-nek? Mondja ki Euler tételét, és ellenőrizze, hogy teljesül a G síkgráfra.
b) Rajzolja le G duálisát úgy, hogy ez szép lerajzolás legyen (ami igazolja a duális gráf síkgráfságát).
c) Színezze jól a G gráfot 4 színnel. [20 pont]

2. a) Definiálja a párosítás, teljes párosítás és javító út fogalmát.
b) Tekintsük az alábbi páros gráfot, és a piros színnel jelölt M párosítást. Keressen javító utat M-re nézve, és javítsa meg a javító út segítségével a párosítást.
(A magyar módszer segíthet a javító út megtalálásában.)
c) Mondja ki a Kőnig-Hall tételt. [20 pont]

3. a) Definiálja az út, kör, Hamilton-út és Hamilton-kör fogalmakat.
b) Mondja ki Dirac tételét.
c) Egy n pontú G egyszerű gráfban minden pont foka legalább n/2, és adott egy P út, ami nem Hamilton-út. Igazolja, hogy ekkor G mohó vagy csavart módon növelhető. (Gondoljon a Dirac-tétel bizonyítására.) [30 pont]

4. a) Definálja a hálózat, folyam, folyam értékének, vágás, vágás kapacitásának fogalmát.
b.) Mondja ki és bizonyítsa be a maximális folyam - minimális vágás tételt. [30 pont]