A vizsgaidõszak minden hetének keddjén vizsgáztatok délután 2 órakor a szobámban. A vizsgára jelentkezés az irodán történik úgy, hogy ott egy ``tételt'' húzunk. A vizsga letételének napja a húzást követõ elsõ kedd.

A vizsga egy ``esszé kérdésbõl'' és egy szóbeli részbõl áll. Az esszé kérdés a tananyag körülbelül egy elõadásnyi részét kéri számon bizonyításokkal és a mélyebb összefüggéseken túl a technikai nehézségek kidogozásával együtt. Az esszé kérdését húzzák a vizsgázók a jelentkezés idején. (Tehát az esszé kérdés kidolgozására egy hete van annak aki kedden jelentkezik vizsgára.) Az esszé kérdésre adott válaszunkat otthon írásban kell kidolgozni. A vizsgáztatás szóbeli része az esszé kérdésre adott dolgozattal kapcsolatban felmerült és az anyag többi részével kapcsolatos kérdések tisztázása. Az anyag többi részének ismeretébõl történõ számadáshoz nem szükséges az összes technikai nehézség és megoldásának memorizálása. Elegendõ a fogalmak, tételek, eredmények biztos ismerete. A nyilvánvaló részek és a bizonyítás vázlatának tudata.

Az esszé kérdés

Az esszé kérdés egy nagyobb kérdésrõl az elõadásokon elhangzott ismeretek teljes leírását kéri. Az ``esszé '' megírásához néhány szempontot sorolok fel segítségül.

A kérdés a benne leírt témáról az összes elõadáson elhangzott anyag (ahol volt ott bizonyításokkal) tárgyalását jelenti.
Az alap gráfelmélet elõadást meghaladó fogalmakat, tételeket pontosan fogalmazzuk meg.
A fogalmazásra, stílusra fordítsunk nagy figyelmet.
Világosan, érthetõen, logikusan építsük fel mondanivalónkat.
Az elõadáson elsõre nehezen érthetõ anyagot próbáljuk úgy ``tálalni '', hogy másoknak már kevesebb problémájuk legyen a gondolat megértésével. A középiskolások számára érthetõ dolgok úgy legyenek megfogalmazva, hogy dolgozatunkból egy középiskolás is értse meg azokat.
Az egyszerû gondolatok az olvasó számára is egyszerûnek, a természetesek természetesnek tûnjenek.
A beadott munka struktúrált legyen.
Motivációra és a nehezebb fogalmak, ötletek fokozatos bevezetésére törekedjünk. Példák szerepeljenek, ha azok segítséget nyújtanak.
Amit fontosnak tartunk azt emeljük ki. Amit a gondolatmenet fõ irányához képest kitérõnek érzünk azt írjuk kisebb betûvel.
Nem a dolgozt hossza számít, hanem minõsége. Technikai részletekben ne vesszünk el. A fontos gondolatok, az áttekintés viszont mindig legyenek az elõtérben.
A cél nem az elõadás írásbeli megismétlése, hanem arról való tanúságtétel, hogy megértettük az anyagot.
Próbáljunk javítani az elõadásban elhangzottak minóségén. Például az elõadásokon elhangzott jelölések nem biztos hogy szerencsések voltak. Próbáljunk olyan jelölést használni ami számunkra a legkifejezõbb. Egyes bizonyítási részek sorrendje lényegtelen, de az elõadáshoz képest felcserélésük könnyebbé, érthetõbbé teszi az olvasó (hallgató) feladatát. Saját magunk által felvetett gondolatokat is érdemes leírni. Minden érdemi plusz az elõadáshoz képest jelentõs elõnyt jelent.

Egy esszé kérdés a következõk közül kerül ki.

Palacsinta gráfok
Kneser-gráfok
Univerzális sorozatok teljes gráfokban
Soros-párhuzamos gráfok definíciói és jellemzése
Soros-párhuzamos gráfok csúcs színezése
Az élkromatikus szám becslései, síkgráfok élszínezése és a négyszínsejtés
Outerplanar gráfok, outerplanar gráfok jellemzése
Okamura--Seymour-tétel
Frank András tétele
Sík gráfok Kuratowski-féle jellemzése
F₂ feletti vektorterek, vágások és Euler-gráfok alterei és ezek bázisai
Sík gráfok MacLane-féle jellemzése
gráfok absztrakt duálisának különbözõ defíníciói és tulajdonságai, sík gráfok Whitney-féle jellemzése (Az elõadáson errõl a jellemzésrõl csak két bizonyításvázlatot ``hadartam'' el. Ezen kérdés kidolgozójána az a (nem túl nehéz) feladata, hogy az elhangzott két vázlatot minél részletesebben dolgozza ki.)
Koebe-tétel
Lipton--Tarjan-tétel sík gráfok szeparálásáról
Wagner-tétel K₅ minort nem tartalmazó gráfok struktúrájáról

A szóbeli vizsga anyaga

Speciális gráfsorozatok

Palacsinta gráfok
- Palacsintagráf fogalma.
- Átmérõ fogalma, a palacsinta gráf átmérõjének naív becslései (alsó és felsõ)
- Az ismertetett becslések kimondása.
- Égetett palacsinta gráf fogalma.
Irodalom:
1. Ervin Gyõry and György Turán, Stack of pancakes, Studia Scientarum Mathematicarum Hungarica, 13(1978), 133--137.
Kneser-gráfok
- A Kneser-gráfok definíciója.
- A Kneser-gráfok kromatikus számának felsõ becslései indoklással.
- A ritkított Kneser-gráf definíciója és a kromatikus számára, kritikusság'ara vonatkozó állítások kimondása.
- A pontok gömbelhelyezésére vonatkozó lemma kimondása.
- Borsuk-tétel kimondása és annak indoklása hogy ebbõl miért következik az állítás.
Irodalom:
1. A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuv Arch. Wisk., 26(1978), 454--461.
Teljes gráfok
- Az univerzális bejáró sorozat fogalma.
- A teljes gráfokra vonatkozó konstrukció leírása, a definiált sorozat hosszának becslése.
- Indokoljuk meg, hogy a konstrukció mélységének miért volt elég O(log n)-et választani.
Irodalom:

Speciális gráfosztályok

Soros-párhuzamos gráfok
- Soros-párhuzamos gráfok kétféle definíciója.
- A kétféle definíció viszonya, indoklás(?) példákon keresztüli demonstrációval.
- Kétszeres összefüggõség különbözõ értelmezései és ezek viszonya.
- Soros-párhuzamosság kiterjesztése nem kétszeresen összefüggõ gráfokra.
- Soros-párhuzamos gráfok jellemzése kizárt minorral.
- Soros-párhuzamos gráfok kromatikus száma legfeljebb 3 (indoklás!).
- Mohó színezési algoritmus és a rá vonatkozó tétel.
- Gráfok élkromatikus számának becslései (indoklással).
- Soros-párhuzamos gráfok élszinezésére vonatkozó tétel.
- Síkgráfok élszínezésének kapcsolata a négyszín tétellel (indoklás).
Irodalom:
1. P.D. Seymour, Colouring series-parallel graphs, {\sl Combinatrica}, {\bf 10}(1990), 379--392.
Outerplanar gráfok
- Éldiszjunkt út probléma, Menger tételeivel való kapcsolat.
- Vágási feltételek, szükségesség indokklással!
- Paritási feltételek, szükségesség indoklással!
- Elégségességi tételek kimondása (Hu-tétel, Seymour-tétel, Okamura--Seymour-tétel, Frank-tétel).
- Indokoljuk meg, hogy Okamura--Seymour tételében miért elegendõ kétszeresen összefüggõ esetben bizonyítani.
- Indokoljuk meg, hogy a bizonyítás során kiválasztott két él létezése esetén miért mûködik az indukció.
- Frank András párosítási lemmájának kimondása.
- Indokoljuk meg, hogy ennek ismeretében miért adódik ki a tétel.
Irodalom:
1. H. Okamura and P. Seymour, Multicommodity flows in planar graphs, J. Combin. Theory Ser. B, 31(1981), 75--81.
2. Anrás Frank, Edge-disjoint paths in planar graphs, J. Combin. Theory Ser. B, 39(1985), 75--81.
Síkgráfok
- Síkgráfok, síkra rajzolt gráfok definíciója.
- Kuratowski-karakterizá;ció kimondása és szükségességének indoklása.
- MacLane-karakterizáció kimondása és szükségességének indoklása.
- Whitney-karakterizáció kimondása és szükségességének indoklása.
- Koebe tételének kimondása.
- A bizonyításban szereplõ ``alfa kalap'' függvény egy-egy értelmûségének indoklása.
- Lipton--Tarjan-tétel kimondása
- Egy ponthalmaz centrumának definíciója és létezésének indoklása.
Irodalom:
1. Lovász László, Kombinatroika problémák és feladatok, 5. fejezet, Typotex Kiadó, Budapest, 1999
2. Hajnal Péter, Gráfelmélet, 10. fejezet Polygon Jegyzet, Szeged, 1997
3. P. Agarwal, János Pach, Combinatorial geometry, Chapter 8., John Wiley & Sons, Inc., New York, 1995.
K₅-t minorként nem tartalmazó gráfok
- Wagner-karakterizáció kimondása
- A karakterizáció ismeretében Wagner ekvivalenciatételének indoklása.
Irodalom:
1. C. Thomassen, Embeddings and minors, 301--349. Chapter 5. a Handbook of Combinatorics volume I. könyvben, edited by R.L. Graham, M. Grötschel and László Lovász, Cambridge, MA, 1995.