A 3 pontú egyszerû gráfok izomorfiatípusainak száma: 4.
A 4 pontú egyszerû gráfok izomorfiatípusainak száma: 11.
A 5 pontú egyszerû gráfok izomorfiatípusainak száma: 34.
További adatok:
A 6 pontú egyszerû gráfok izomorfiatípusainak száma: 156.
A 7 pontú egyszerû gráfok izomorfiatípusainak száma: 1044.
A 8 pontú egyszerû gráfok izomorfiatípusainak száma: 12346.
A 9 pontú egyszerû gráfok izomorfiatípusainak száma: 274668.
Kis pontszám esetén a munkánkat nagyban megkönnyíti, hogy ha az élszámot egy rendezõ elvként követjük. Továbbá észrevesszük, hogy a k élû gráfok és az n(n-1)/2-k élû gráfok izomorfiatípusainak száma egyenlõ. Ezt a komplementer gráf fogalmának bevezetésével tehetjük pontossá.
Definíció: Egy G egyszerû gráf komplementere az a gráf, amley csúcshalmaza V(G) és két pont akkor és csak akkor van összekötve, ha G-ben nincs összekötve.
Definíció: Egy gráf fokszámsorozata pontjai fokszámáinak rendezett (növekvõ) sorozata.
1. feladat: Lehet-e 0,1,2,3,4,5,6,7,8,9 egy gráf fokszámsorozata?
2. feladat: Lehet-e 0,1,2,3,4,5,6,7,8 egy gráf fokszámsorozata?
3. feladat: Lehet-e 0,1,2,3,4,5,6,7,8 egy egyszerû gráf fokszámsorozata?
4. feladat: Legyen S egy ponthalmaz a G gráfban. Fejezzük ki az S-beli pontok fokszámainak összegét.
Válasz: Az S-beli élek számának kétszereséhez hozzáadva az S-beli pontokat az S-en kívüli pontokkal összekötõ élek számát.
Definíció: Egy G gráfot páros gráfnak nevezünk, ha pontjai két diszjunkt osztályba vannak sorolva úgy, hogy tetszõleges él két végpontja különbözõ osztályba esik.
Megjegyzés: Az elõzõ feladatból (de józan gondolkodással is egyszerûen) adódik, hogy egy páros gráfra az egy-egy csuc'sosztályba esõ csúcsok fokszámainak összege azonos és egyenlõ az élek számával.
5. feladat: Lehet-e 3,3,3,3,3,3,4,6,6,6,6,6,6,6 egy páros gráf fokszámsorozata?
6. feladat: Bizonyítsuk be, hogy minden G egyszerû gráf esetén G vagy komplementere összefüggõ.
7. feladat: Bizonyítsuk be, hogy ha egy 2n pontú egyszerû gráf minden foka legalább n, akkor a gráf összefüggõ.
Otthoni munkára javaslat: Gondolkozzunk az utolsó feladaton, amely megoldására nem volt idõ.