!!: Fontos definíció, TUDNI KELL

!: Alapösszefüggés

!*: [általában] Tétel, kimondani tudni kell, ha van triviális iránya, akkor azt is tudjuk azonosítani, de bizonyítása (amennyiben szerepelt előadáson) csak akkor, ha a többi dolog már jól megy

**: Csak akkor, ha a többi dolog jól megy

• Gráf, egyszerű gráf, hurokélnélküli gráf !!
• Fokszámok, fokszámsorozat !!
• Realizációs tételek !*
• Cayley tétele !*
• Cayley tételének kombinatorikus bizonyítása **
• Pont-él illeszkedési mátrix !!
• Pont-él illeszkedési mátrix négyzetes aldeterminánsai **
• Kirchoff-tétel !*
• Párosítások gráfokban !!
• Véletlen algoritmus teljes párositás létezésének tesztelésére páros gráfokban !*
• Schwartz-lemma kimondása !*
• Javító út párosításokra !!
• Javító út léte és a párosítás optimalitása közötti kapcsolat !*
• Javító út keresés javító útkezedemények mohó növelesével (magyar módszer): gyökerek, címkék (külső/belső), kereső erdő, sikeres/sikertelen keresés !!
• Edmonds-algoritmus !*
• Tutte-akadály !!
• Tutte-akadály és teljes párosítások kapcsolata !*
• Tutte-tétel !*
• Tutte-akadály viszonya a legnagyobb párosítás méretéhez !*
• Berge-formula !*
• Csúcsszínezés, élszínezés, kromatikus szám, élkromatikus szám !!
• Hajós-operációk !!
• Hajós-operációk viszonya a nem-k-színezhetőséggel !*
• Derékbőség !!
• Derékbőség és kromatikus szám kapcsolata !*
• Vizing-tétel, Shannon-tétel !*
• Shannon-tétel bizonyítása **
• Síkgráfok: lerajzolás, szép lerajzolás !!
• Síkgráfok tartomány színezése, dualitás !!
• Euler tétele !*
• K₅ és K_3,3 nem síkgráfok !*
• Topológikus részgráf, minor !!
• Kuratowski-tétel, Wagner-tétel !*
• Metszési paraméter !!
• Metszési lemma !*
• Metszési lemma bizonyítása **
• Metszési lemma alkalmazásai **
• k-szorosan élösszefüggő gráfok, k-szorosan összefüggő gráfok !!
• k-szorosan élösszefüggő gráfok, k-szorosan összefüggő gráfok jellemzése !!
• Ponthalmaz határa !!
• Ponthalmaz határának kapcslata az élösszefüggéssel !
• Minimális k-szorosan élösszefüggő gráfok *
• Szubmoduláris egyenlőtlenség ! *
• Turán-gráfok !!
• ext(n;T) függvény !!
• ext(n;F) becslései, ha F fa !*
• Erdős-Stone-tétel !* (csak kimondás, egyszerű irány)
• Ramsey-számok definíciója (két szín, c szín, k-asok szíbezése) !!
• Ramsey-számok felső becslései
• Erdős-Szekeres tétel !*
• Erdős-Szekeres tétel bizonyítása **
• Sperner-rendszer, Sperner-tétel kimondása !!
• LYM egyenlőtlenség !!
• Sperner-tétel !*
• Erdős-Ko-Rado tétel !*