A témák leírása bonyolultnak tűnik. Én azonban arra vagyok kiváncsi, hogy az alapfogalmakkal, alaptételekkel tisztában vannak-e. A világos beszéd, pontos fogalmazás nagy plusz. Bizonyításokban csak akkor merülünk el, ha valaki jobb jegyet kér. Egy fogalmat, definíciót egy példa mindig érthetőbbé tesz.

1. • Definiálja egy gráf fokszámsorozatát, egy számsorozat realizálhatóságát. Mondja ki a Havel-Hakimi-tételt. Igazolja is. Mikor realizálható egy természetes számokból álló sorozat egyszerű gráffal? Válasza egy algoritmus legyen.
   • Definiálja a térkép fogamát. Írja le a térkép színezési problémát. Mondja ki a négy-szín-sejtést. Adja meg a sejtés élszínezési változatát. Igazolja, hogy ez ekvivalens a négy-szín-tétellel.
2. • Definiálja egy gráf fokszámsorozatát, egy számsorozat realizálhatóságát. Mikor realizálható egy sorozat fával? Igazolja is állítását. Adott csúcshalmaz minden eleméhez egy-egy természetes számot rendelünk úgy hogy a kiosztott számok sorozata fával realizálható legyen. Hány realizáló fa létezik? Hány fa létezik adott csúcshalmazon? Igazolja állításait.
   • Definiálja a metsző halmazrendszer fogalmát. Mekkora lehet egy n elemű halmaz feletti metsző halmazrendszer élszáma? Igazolja válaszát. Mi a helyzet k-uniform halmazrendszerek felett? monja ki az Erdős-Ko-Rado-tételt. Ismertesse bizonyítását.
3. • Mondja ki Cayley tételét. Adjon rá egy bijektív bizonyítást.
   • Definiálja a Sperner-rendszer fogalmát. Adjon példákat Sperner-rendszerre. Mondja ki Sperner tételét. Definiálja egy halmazrendszer f-vektorát. Igazolja Sperner tételét.
4. • Definiálja egy hurokélmentes gráf és egy hurokélmentes irányított gráf pont-él-illeszkedési mátrixát. Hogy kapható meg egy gráf pont-él-illeszkedési mátrixából egy irányításának pont-él-illeszkedési mátrixa? Írja le, hogy egy hurokélmentes G egy irányításának pont-él-illeszkedési mátrixának mely (|V|-1)x(|V|-1) méretű részmátrixai lesznek teljes rangúak. Írja fel Kirchoff formuláját.
   • Definiálja a homogén halmaz fogalmát. Mondja el a Ramsey-témakör színezéses nyelvezetét. Definiálja a Ramsey-számokat. Definiálja a Ramsey-számokat több szín esetére, illetve k-asok esetére. Adjon egy algoritmust, amely nagy homogén halmazt számol ki több szín esetén. Milyen becslés adódik a Ramsey-számokra.
5. • Mit értünk egy gráfban egy párosítás alatt? Milyen optimalizálási probléma kapcsolódik a párosítás fogalmához? Írjuk le a mohó algoritmust, amely nagy párosítást keres. Mit mondhatunk az output méretéről? Igazolja ezt.
   • Mondja ki Wagner tételét. Az indirekt bizonyítás kezdetén egy minimális ellenpéldát vettünk. Mit mondhatunk erről az ellenpéldáról? Adott egy gráfelméleti kör és csúcsainak egy piros és kék részhalmaza (nem feltétlenül diszjunktak). Definiálja mikor nevezhetjük a két színhalmazt szeparálhatónak. Mondja ki az előadáson leírt, a definícióval ekvivalens leírást.
6. • Mit értünk egy gráfban egy párosítás alatt? Milyen optimalizálási probléma kapcsolódik a párosítás fogalmához? Definiálja a javító út fogalmát (egy párosításra nézve). Hogyan kereshetünk javító utat egy páros gráfban?
   • Definiálja egy pont- és egyenesrendszer illeszkedési paraméterét. Mondja ki a Szemerédi-Trotter-tételt. Igazolja a tételt. A felhasznált segédeszközöket/tételeket pontosan írja le (azokat bizonyítani nem kell).
7. • Mit értünk egy gráfban egy párosítás alatt? Milyen optimalizálási probléma kapcsolódik a párosítás fogalmához? Mit értünk egy gráfban egy lefogó ponthalmaz alatt? Milyen optimalizálási probléma kapcsolódik a lefogó ponthalmaz fogalmához? Adott egy M párosítás és egy L lefogó ponthalmaz. Milyen körülmények között lehetünk biztosak, hogy M optimális párosítás? Igazolja, hogy az előadáson ismertetett javító út keresés páros gráfokban teljes.
   • Hogyan definiáltuk a k-szorosan élösszefüggő gráfokat. Definiálja egy csúcshalmaz határát. Definiálja a k-szorosan élösszefüggő gráfokat a határ fogalomra alapozva. Mikor mondjuk, hogy egy gráf minimális k-szorosan élösszefüggő gráf? Mondja ki Mader tételét. Mondja ki a szubmoduláris egyenlőtlenséget. Igazolja is.
8. • Mit értünk egy gráfban egy párosítás alatt? Milyen optimalizálási probléma kapcsolódik a párosítás fogalmához? Mit értünk egy gráfban egy lefogó ponthalmaz alatt? Milyen optimalizálási probléma kapcsolódik a lefogó ponthalmaz fogalmához? Adott egy M párosítás és egy L lefogó ponthalmaz. Milyen körülmények között lehetünk biztosak, hogy M optimális párosítás? Igazolja, hogy az előadáson ismertetett javító út keresés páros gráfokban teljes.
   • Definiálja egy gráf metszési paraméterét. Mi K₃, K₄, K₅, K_2,3 és K_3,3 metszési paramétere? Bizonyítsa be, hogy |E|-3|V| egy alsó becslés a metszési számra. Mondja ki a metszési lemmát. Igazolja is.
9. • Mit értünk egy gráfban egy párosítás alatt? Milyen optimalizálási probléma kapcsolódik a párosítás fogalmához? Definiálja a javító út fogalmát (egy párosításra nézve). Hogyan kerestünk javító utat egy gráfban (Edmonds)?
   • Definiálja gráfok részgráfját, topologikus részgráfját, minorját. Mit tud mondani ezen "részekről" ha síkgráfnál vizsgálja a fogalmakat? Adjon példákat nem síkgráfokra. Mondja ki Kuratowski tételét. Mondja ki Wagner tételét.
10. • Mit értünk egy gráfban egy párosítás alatt? Milyen optimalizálási probléma kapcsolódik a párosítás fogalmához? Definiálja a javító út fogalmát (egy párosításra nézve). Mit értünk egy Tutte-akadály alatt. Legyen M egy párosítás és T egy Tutte-akadály. Milyen körülmények között lehetünk biztosak, hogy M optimális párosítás? Igazolja, ha Edmonds javító út keresése sikertelen, akkor az aktuális párosítás maximális.
    • Mit értünk egy szép lerajzolás alatt? Definiálja egy szépen lerajzolt gráf eseteén a tartománynak, illetve egy tartomány határának fogalmát. Definiálja egy szépen lerajzolt gráf duálisának fogalmát. Adjon Adjon kapcsolatokat az eredeti és duális gráf paramétereinek kapcsolataira.
11. • Mit értünk egy gráfban egy párosítás alatt? Milyen optimalizálási probléma kapcsolódik a párosítás fogalmához? Legyen G egy kiegyensúlyozott, egyszerű páros gráf, legyen B a páros szomszédági mátrixa. Mire következtethetünk, ha det B értéke nem 0? Adjon egy randomizált algoritmust, amely kiegyensúlyozott páros gráfokat teszteli: van-e teljes párosítás benne. Mondja ki a Schwartz-lemmát. Mi a köze a lemmának az algoritmushoz?
    • Definiálja a k-szorosan élösszefüggő és k-szorosan összefüggő gráfokat. Mi ezen fogalmak kapcsolata? Mondja ki Menger tételének négy változatát. Jellemezze alternatív módon a a k-szorosan élösszefüggő gráfokat.
12. • Definiálja egy gráf jó színezésének fogalmát. Mi az ehhez kapcsolódó optimalizálási feladat? Mondja ki a Hajós tételt. Bontsa a tételt két következtetésre. Melyik az egyszerűbb? Igazolja ezt.
    • Definiálja az ext(n;T) függvényt. Becsülje a függvény értékét alúlról és felülről is, ha T-nek 1 vagy két éle van. Igazolja, ha a tiltott T gráf fa, akkor ext(n;T) az n egy lineáris függvényével felülről becsülhető.
13. • Definiálja egy gráf jó színezésének fogalmát. Mi az ehhez kapcsolódó optimalizálási feladat? Mondja ki a Hajós tételt. Bontsa a tételt két következtetésre. Melyik az egyszerűbb? Igazolja ezt.
    • Definiálja egy valós számokból álló halmaz összeg és szorzat halmazát. Mondja ki az Elekes-tételt. Igazolja a tételt. A felhasznált segédeszközöket/tételeket pontosan írja le (azokat bizonyítani nem kell).
14. • Definiálja egy gráf jó színezésének fogalmát. Mi az ehhez kapcsolódó optimalizálási feladat? Definiálja egy gráf derékbőségét. Mondja ki a fenti két fogalommal kapcsolatos Erdős-tételt. Igazolja ezt.
    • Definiálja az ext(n;T) függvényt. Becsülje meg felülről az ext(n;C₄) függvényt. Felső becslésének nagyságrendjét írja le.
15. • Definiálja egy gráf jó élszínezésének fogalmát. Mi az ehhez kapcsolódó optimalizálási feladat? Mondja ki Shannon és Vizing tételét. Az egyiket bizonyítsa be.
    • Definiálja a homogén halmaz fogalmát. Mondja el a Ramsey-témakör színezéses nyelvezetét. Definiálja a Ramsey-számokat. Definiálja a Ramsey-számokat több szín esetére, illetve k-asok esetére. Adjon alkalmazását a Ramsey-tételnek.