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 A^k 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]