4. FEJEZET: Szimmetria és aszimmetria, I.

Feladat: 4.1.
Izomorf-e egymással . ábrán látható két gráf?
 

Feladat: 4.2.
Izomorf-e egymással a 4.2. ábrán látható két gráf?
 

Feladat: 4.3.
Egy hétpontú körbe behúztuk a ,,rövidebb" átlókat, egy másik hétpontú körben pedig behúztuk a ,,hosszabb" átlókat. Izomorf-e az így kapott két hétpontú gráf? L. . ábrát!
 

Feladat: 4.4.
Izomorf-e egymással ábrán látható két gráf?
 

Feladat: 4.5.
Van-e két, egymással nem izomorf ötpontú 2-reguláris gráf?
 

Feladat: 4.6.
Van-e két, egymással nem izomorf 2-reguláris hatpontú gráf?
 

Feladat: 4.7.
Izomorf-e egymással bármely két hatpontú, 2-reguláris összefüggő gráf?
 

Feladat: 4.8.
a) Van-e két, egymással nem izomorf 3-reguláris hétpontú gráf? b) Hány egymással nem izomorf hétpontú 4-reguláris gráf van?
 

Feladat: 4.9.
Melyik állítások igazak az alábbiak közül: Ha két gráf izomorf, akkor a) azonos a kromatikus számuk; b) ugyanakkora az átmérőjük; c) mindkettőben ugyanannyi a független pontok maximális száma.
 

Feladat: 4.10.
Izomorf-e egymással a következő három gráf: a) a kocka gráfja, b) az a nyolcpontú páros gráf, amelyet úgy kapunk a K4,4 teljes páros gráfból, hogy elhagyunk egy teljes párosítást (. ábra), c) az a nyolcpontú gráf, amely egy nyolc hosszú körből áll, ennek pontjai sorban a Pi pontok, i=1,2,…,8, a gráf éle még a következő négy átló: P1 P3 , P2 P4 , P5 P7 , P6 P8 (4.10. ábra).
 

Feladat: 4.11.
Igaz-e, hogy izomorf gráfok komplementerei is izomorfak?
 

Feladat: 4.12.
Hány különböző, egymással nem izomorf n pontú egyszerű gráf van, ha a) n=3, b) n=4?
 

Feladat: 4.13.
Számoljuk meg, hány egymással nem izomorf 2-reguláris n pontú egyszerű gráf van az n=4,5,6,7,8,9 esetben!
 

Feladat: 4.14.
Igaz-e, hogy ha két összefüggő, hatpontú gráfban a fokszámok rendre 1,1,1,1,3,3, akkor a két gráf izomorf?
 

Feladat: 4.15.
[4], 14. old. Igaz-e, hogy ha két összefüggő, hétpontú gráfban a fokszámok rendre 1,1,1,1,2,3,3, akkor a két gráf izomorf?
 

Feladat: 4.16.
Hány egymással nem izomorf hétpontú fa van, amelyben van negyedfokú pont?
 

Feladat: 4.17.
Hány olyan nem-izomorf tízpontú fa van, amelyben van két, legalább ötödfokú pont?
 

Feladat: 4.18.
Hány olyan nem-izomorf 2k pontú fa van, amelyben van két, legalább k-adfokú pont?
 

Feladat: 4.19.
Hány olyan nem-izomorf tízpontú összefüggő gráf van, amelyben van két-két negyed- és másodfokú pont van, a többi pont pedig elsőfokú?
 

Feladat: 4.20.
Bizonyítsuk be, hogy a K.II.8.13. feladat megoldásában kapott gráf . ábrán látható Petersen-gráf
 

Feladat: 4.21.
Melyik ismert gráf a KG(4,2) Kneser-gráf komplementere?
 

Feladat: 4.22.
Melyik ismert gráf a KG(5,2) Kneser-gráf?
 

Feladat: 4.23.
Adott két n pontú egyszerű gráf. Az egyik gráf mindegyik n-1 pontú feszített részgráfjához van a másiknak ezzel izomorf n-1 pontú feszített részgráfja. Következik-e ebből, hogy a két gráf is izomorf?
 

Feladat: 4.24.
Két négypontú gráf minden hárompontú feszített részgráfja két élt tartalmaz. Következik-e ebből, hogy a két négypontú gráf izomorf?
 

Feladat: 4.25.
Egy G gráfról tudjuk, hogy bármely pontját elhagyva egymással izomorf részgráfokat kapunk. Következik-e ebből, hogy a gráf reguláris?
 

Feladat: 4.26.
G és G' azonos pontszámú d-reguláris gráfok. Tudjuk, hogy G-nek van olyan x pontja és G'-nek van olyan x' pontja, amelyre G-x és G-x' izomorfak. Következik-e ebből, hogy G és G' is izomorf?
 

Feladat: 4.27.
[4], 14. old. Mely G páros gráfok izomorfak a komplementerükkel?
 

Feladat: 4.28.
[4], 14. old. Mely fák izomorfak a komplementerükkel?
 

Feladat: 4.29.
Azt vizsgáljuk, hogy milyen n-ekre van olyan n pontú egyszerű gráf, amely izomorf saját komplementerével. a) Döntsük el a kérdést az n=1,2,3,4,5,6,7 esetekben! b) Döntsük el a kérdést n=8,9 esetben!
 

Feladat: 4.30.
Döntsük el általában, hogy n milyen értékeire van olgyan n pontú egyszerű gráf, amely izomorf a komplementerével!
 

Feladat: 4.31.
[4], 14. old. Legyen n páratlan egész szám és legyen G egy n pontú gráf, amely izomorf a komplementerével. Bizonyítandó, hogy van olyan pontja, amelynek (n-1)/2 a fokszáma.