Megoldás: 2.20
Ha a gráf minden hárompontú feszített részgráfjában két él van, ez azt jelenti, hogy a komplementer gráf minden feszített részgráfjában pontosan egy él van.
A komplementergráfban tehát minden pont foka nulla vagy egy. (Ha
x-nek két szomszédja volna a komplementerben,
y és
z, akkor az
x,y,z által feszített részgráfra nem teljesülne a feltétel.) Ha a gráfnak legalább öt pontja van, akkor ez azt is jelenti, hogy a komplementergráfban van három pont, amelyek között nem fut él, ez azonban ellentmond a feltételünknek.
Azt kaptuk, hogy egy ilyen gráf pontszáma legfeljebb négy lehet. A kétpontú gráfok triviálisan jók (nincs kikötés) és a hárompontú, kétélű gráf is jó. A négypontú gráfok közül a ,,négyszög" az egyetlen jó. Összesen tehát négy ilyen gráfot találtunk.