Megoldás: 9.24
Három pont nem elég. Ha ugyanis vesszük a kockának négy, párhuzamos élét, ezek közül semelyik kettőnek nincs közös csúcsa (vagyis a kocka gráfjának négy független élét alkotják). Ha tehát három pontot hagyunk el a kocka gráfjából, akkor e négy él valamelyike még biztosan megmarad.
Viszont ha négy olyan csúcsot hagyunk el, amelyek szabályos tetraédert alkotnak, akkor a megmaradó négy pont között nem fut él (azok alkotják a másik szabályos tetraédert). Ugyanezt megfogalmazhatjuk a következőképpen is: a kocka gráfja páros gráf, amelynek mindkét osztálya négy pontból áll (a megfelelő csúcsok egy-egy szabályos tetraédert alkotnak). Bármelyiket elhagyva csak a másik osztály pontjai maradnak és azok független ponthalmazt alkotnak.