Megoldás: 2.6
a) Ha
n legalább hét, akkor van
n pontú, 6-reguláris egyszerű gráf.
b) Ha
k=2l páros szám és
n>2l, akkor van
n-pontú
k-reguláris egyszerű gráf. (A konstrukciót ismét társasági ismeretségekre egyszerű elmondani: leültetjük az
n embert egy kerek asztal köré és mindenkit összeismertetünk az
l darab bal és
l darab jobb oldali szomszédjával.)