- Rajzolj 1, 1, 2, 2, 3, 3 fokszámú egyszerű gráfokat. Több különböző (nem izomorf) megoldás is van!
- Lehetnek-e az alábbiak egy gráf csúcsainak fokszámai?
- 3, 4, 4, 4, 5
- 0, 2, 2, 2, 4
- 1, 1, 2, 2, 4
- 1, 1, 2, 4, 4
- 1, 1, 2, 3, 4
- Igazoljuk, hogy bármely fa esetén az élek és pontok számának szorzata páros!
- Rajzold le az összes nem izomorf 3, 4 és 5 pontú fát!
- Igazoljuk, hogy bármely legalább öt csúcsú egyszerű gráf vagy komplementere tartalmaz kört!
- Egy héttagú társaságban a házigazda mindenkit ismer, a több vendég pedig pontosan 2-2 embert ismer. Szemléltessük ezt az ismeretségeket gráfként!
- Igaz-e, hogy ha egy gráf izomorf a komplementerével, akkor minden pontjának foka páros?
- Mely fák izomorfak saját komplementerükkel?
- Bizonyítsuk be, hogy egy n pontú fában a másodfokú pontok száma nem lehet pontosan n-3.
- Igaz-e a következő állítás: Ha egy 2n pontú egyszerű G gráfban minden pont foka legalább n, akkor G összefüggő.
- Legyen G hatpontú egyszerű gráf, melyben minden pont foka legalább négy. Bizonyítsuk be, hogy G bármely négy pontja (alkalmas sorrendben) egy kört alkot.
