1) Definiálja a hálózat, folyam, folyam értékének fogalmát.

Írja le mit értünk a folyamra vonatkozó javító úton és indokolja miért használjuk rá javító jelzőt.

Írja le hogyan kerestünk maximális értékű folyamot egy adott hálózatban.

Indokolja, ha minden él kapacitása $1$, akkor az eljárás leáll és mondja meg mit tudhatunk az output-folyam által az egyes élekhez rendelt számokról.

2) Definiálja mikor nevezünk egy ponthalmazt Tutte-akadálynak.

Indokolja meg mit akadályoz meg egy Tutte-akadály léte.

Legyen $T$ egy Tutte-akadály. Írjon fel egy becslést a legnagyobb párosítás méretére $T$ függvényében.

Futassa az Edmonds-algoritmust egy $M$ párosítással. Tegyük fel, hogy zsugorítás nélkül, sikertelen kereséssel leáll az algoritmus. Bizonyítsa be, hogy a párosítás optimális.

3) Definálja egy gráf élszínezését, jó élszínezését és írja le milyen optimalizálási kérdést vizsgáltunk erre vonatkozólag.

Milyen kapcsolatban áll az élkromatikus szám a maximális fokszámmal. Írjon le egy gráf osztályt (bzionyítás nélkül) ahol egyenlőség teljesül.

Vizing-tétel bizonyításában egy (parciális) élszínezést átszíneztünk, majd kiterjesztettük a színezést. Írja le, hogyan színeztünk át (az élek, színek választására nem vagyok kiváncsi).

4) Definiálja mikor nevezünk egy gráfot síkgráfnak.

Vegyünk fel három diszjunkt háromszöget, majd egy új (tizedik) csúcsot, amit kössünk össze egy-egy ponttal mindegyik háromszögről. Síkgráfot kaptunk-e? Ha nem, indokoljuk meg miért. Ha igen, akkor rajzoljuk le szépen, azonosítsuk tartományait, a tartományok határának hosszait írjuk fel.

Mondja ki és bizonyítsa be Euler-tételét.

Igazolja, hogy a Petersen-gráf nem síkgráf.