A végső tematika az utolsó előadás végén pontosítva lesz.

• Bijekció, párba állító leképezés
• Három alapelv
• Részhalmazok száma
• k elemű részhalmazok száma
• Polinomok szorzása, binomiális tétel
• Sorbaállítások
• Sorbaállítások száma
• Inverziók
• k inverzióval rendelkező sorbaállítások
• Átrendezések, permutációk
• Ciklusok
• k ciklussal rendelkező permutációk száma
• Multihalmazok
• Multihalmazok részhalmazai, sorbaállításai
• Formális hatványsorok és alapműveleteik
• ((ⁿ_k)) számok (k=0,1,2,3,..) generátorfüggvénye
• Szita módszer
• Szita módszer alkalmazásai
• Generátorfüggvény módszer: Fibonacci-számok
• Generátorfüggvény módszer: lineáris rekurzió
• Generátorfüggvény módszer: Catalan-számok
• Catala-számok rekurziója, formulája kombinatorikus módszerekkel
• Egyszerű gráf, hurokél-nélküli gráf, gráf fogalma
• Fokszám fogalma, fokszámokra vonatkozó egyszerű állítások
• Séta
• Elérhetőség reláció és ennek ekvivalenciareláció volta
• Csúcsok és élek elhagyása gráfokból, feszített részgráf, részgráf
• Gráfok komponensei
• Összefüggő gráfok
• Fák; ekvivalens definíciók
• Feszítőfa
• Ághajtás
• Gyökeres fák
• Vonal, Euler-vonal fogalma
• Vonal növelései
• Euler-tétel
• Út, kör
• Hamilton-kör, Hamilton-út
• Utak növelése
• Hosszú út keresésére vonatkozó algoritmus; Dirac-tétel
• Gráfok színezése
• Két-színezhető gráfok jellemzése
• Mohó színezési algoritmus
• Alkalmazások: nem reguláris összefüggő gráfok, síkgráfok színezése
• Kempe-átszínezés
• Alkalmazások: síkgráfok színezése
• Klikkek és kapcsolata a színezéssel
• Példa háromszög nélküli, nagy kromatikus számú gráfokra
• Párosítások
• Mohó párosítási algoritmus
• Lefogó ponthalmazok és kapcsolata a párosításokkal
• Javító út
• Kőnig-akadály
• Páros gráfokra vonatkozó párosítási tételek
• Független ponthalmaz, klikkek, komplementer gráf
• Mentel-tétel és bizonyítása
• Turán-gráfok
• Turán-tétel kimondása
• Ramsey-tétel
• Ramsey-számok
• R(3) Ramsey-szám meghatározása