Az igaz, hogy minden olyan térkép, amit csak négy színnel lehet színezni, abban van 4 olyan régió, hogy mindegyik érinti mindegyiket?

Nem, például képzeld el az ábrádon szereplő térképet úgy, hogy a piros háromszög helyett egy ötszög van. Avagy egy C5 (5-hosszú kör) közepébe rakj még egy pontot, amit mindegyik csúccsal összekötsz. Ebben nem lesz K4 (teljes négyes), viszont kell 4 szín a színezéséhez.

Magyarul az a kérdés, hogy ha egy síkbarajzolható gráf csúcsai 4 színnel színezhetőek, akkor a gráfban van négy csúcsú teljes részgráf. A válasz az, hogy nem; ha egy szabályos ötszög szimmetriaközéppontját összekötöd a csúcsaival, akkor a kapott gráf csúcsait csak 4 színnel tudod színezni, mégsincs benne K4. A gráfhoz tartozó térkép úgy néz ki, hogy egymásba rajzolsz két egybevágó és egyállású ötszöget, és a két ötszög által alkotott köztes részt felbontod trapézokra úgy, hogy a legközelebbi csúcsokat kötöd össze.

2-es, az az állítás megfordítása, amit te írsz; az igaz, hogy ha van 4 egymást érintő régió, akkor kell 4 szín, de itt az volt a kérdés, hogy ha 4 színnel színezhető a térkép, akkor van-e négy tartomány, hogy azok kölcsönösen érintik egymást.

Elvileg van valami, mert egyedül a 3 színnel való színezhetőség NP-probléma.