1. a) Definiálja a k-szoros összefüggőség és k-szoros élösszefüggőség fogalmakat.
b) Mutasson egy olyan gráfot, ami kétszeresen élösszefüggő, de nem kétszeresen összefüggő.
c) Mondja ki Menger tételeit. [20 pont]
2. a) Adja meg az ábrán látható G gráf A szomszédsági mátrixát.
b) Milyen gráfelméleti jelentése van az Ak mátrix elemeinek? (Indokolás nélkül.)
c) Írja fel azt a Kirchhoff-formulában szereplő mátrixot, melynek determinánsa G feszítőfáinak számát adja. [20 pont]
3. a) Definiálja a párosítás, teljes párosítás és Tutte-akadály fogalmakat.
b) Mondja ki Tutte tételét. Igazolja az egyszerűbb irányát (ha van Tutte-akadály egy gráfban, akkor ...). [30 pont]
4. a) Igazolja, hogy tetszőleges G egyszerű gráfra χ(G)≥ω(G).
b) Bizonyítsa be, hogy egy háromszögmentes egyszerű gráf kromatikus száma tetszőlegesen nagy lehet. [30 pont]