1. a) Definiálja az összefüggőség, fa, feszítőfa fogalmakat.
b) Adjon meg egy feszítőfát az ábrán látható gráfban.
c) Hány feszítőfája van az n pontú teljes gráfnak? (Bizonyítás nélkül.) n=3-ra ellenőrizzük az előző választ K₃ feszítőfáinak felrajzolásával. [20 pont]

2. a) Definiálja a klikkek és független ponthalmazok, ω(G) és α(G) fogalmakat.
b) Rajzolja fel a 7 pontú 3 részes Turán gráfot, T_7,3-at, és határozza meg ω(T_7,3)-at (indoklással).
c) Mondja ki Turán tételét. [20 pont]

3. a) Definálja egy egyszerű gráf jó színezésének és kromatikus számának fogalmát.
b) Igazolja, hogy egy nem reguláris, összefüggő egyszerű gráf kromatikus száma felülről becsülhető a maximális fokszámmal.
c) Mondja ki Brooks tételét. [30 pont]

4. a) Definiálja a séta, vonal, Euler-vonal és Euler-körvonal fogalmakat.
b) Mondjon szükséges és elégséges feltételt arra, hogy egy gráfban létezzen Euler-körvonal. A szükséges feltételt (a tétel egyszerűbb irányát) bizonyítsa is be.
c) Igazolja, hogy tetszőleges összefüggő egyszerű gráfban létezik olyan körséta, amely minden élen pontosan kétszer halad végig.
(Megoldás: A kínai postás problémájánál tanult módszer szerint duplázzunk meg minden élt, azaz minden élt helyettesítsünk két párhuzamos éllel. A kapott gráf összefüggő lesz, és minden pontjának foka páros, így Euler tétele szerint létezik benne Euler-körvonal, amit az eredeti gráfba "visszavetítve" egy kívánt körsétát kapunk.) [30 pont]