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_3 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).
d.) 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]