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?
Megoldás: 4.25
Legyen a
G gráf egy tetszőleges pontja
x. A
G-x gráf élszámát jelöljük
k-val, az egész gráf élszámát jelöljük
e-vel. Ekkor
x fokszáma
e-k. A feltétel szerint
k minden
x-re azonos, hiszen
G-x minden
x-re izomorf. Ebből következik, hogy
e-k is ugyanaz minden
x-re, tehát a gráf reguláris.
Megjegyzés. Csak annyit használtunk, hogy bármely pont elhagyásával keletkező részgráf élszáma azonos.