Feladat: 8.27.
** Van-e olyan
n, amelyre van olyan pontú, 2-átmérőjű gráf, amelyben minden pont foka legalább három és élszáma
2n-5?
Megoldás: 8.27
Csak
n≥10 esetén lehet ilyen gráf. Az
n=10 esetben a Petersen gráfnak pontosan 15 éle van és 2 az átmérője. A
8.26. feladat megoldásának a) részét kissé pontosítva belátható, hogy elég nagy
n-ekre már nincs ilyen gráf.