Teorema_e_4_ngjyrave
Formulimi i saktë i teoremës
Deklarata intuitive e teoremës së katër ngjyrave - "duke pasur parasysh çdo ndarje të një plani në rajone të afërta, rajonet mund të ngjyrosen duke përdorur më së shumti katër ngjyra në mënyrë që asnjë rajon fqinj të mos ketë të njëjtën ngjyrë" - duhet të interpretohet në mënyrë të përshtatshme për të qenë e saktë. Së pari, rajonet janë ngjitur nëse ndajnë një segment kufitar; dy rajone që ndajnë vetëm pika kufitare të izoluara nuk konsiderohen fqinjë. Së dyti, rajonet e çuditshme, si ato me sipërfaqe të kufizuar, por me perimetër pafundësisht të gjatë, nuk lejohen; hartat me rajone të tilla mund të kërkojnë më shumë se katër ngjyra. (Për të qenë të sigurt, ne mund të kufizojmë në rajonet, kufijtë e të cilëve përbëhen nga shumë segmente të vijës së drejtë. Lejohet që një rajon të rrethojë tërësisht një ose më shumë rajone të tjera.) Vini re se nocioni i "rajonit të afërt" (teknikisht: nëngrup i hapur i lidhur i aeroplanit) nuk është i njëjtë me atë të një "vendi" në hartat e rregullta, pasi vendet nuk duhet të jenë të afërta (p.sh., Provinca Cabinda si pjesë e Angolës, Nakhchivan si pjesë e Azerbajxhanit, Kaliningrad si pjesë e Rusisë dhe Alaska. si pjesë e Shteteve të Bashkuara nuk janë të ngjitura). Nëse kërkojmë që i gjithë territori i një vendi të marrë të njëjtën ngjyrë, atëherë katër ngjyra nuk janë gjithmonë të mjaftueshme. Për shembull, merrni parasysh një hartë të thjeshtuar: Në këtë hartë, dy rajonet e emërtuara A i përkasin të njëjtit shtet. Nëse do të donim që ato rajone të merrnin të njëjtën ngjyrë, atëherë do të kërkoheshin pesë ngjyra, pasi të dy rajonet A së bashku janë ngjitur me katër rajone të tjera, secila prej të cilave është ngjitur me të gjitha të tjerat. Detyrimi i dy zonave të veçanta që të kenë të njëjtën ngjyrë mund të modelohet duke shtuar një 'dorezë' që i bashkon ato jashtë planit. Një ndërtim i tillë e bën problemin të barabartë me ngjyrosjen e një harte në një torus (një sipërfaqe e gjinisë 1), e cila kërkon deri në 7 ngjyra për një hartë arbitrare. Një ndërtim i ngjashëm zbatohet gjithashtu nëse një ngjyrë e vetme përdoret për zona të shumta të shkëputura, si për trupat ujorë në hartat reale, ose ka më shumë vende me territore të shkëputura. Në raste të tilla mund të kërkohen më shumë ngjyra me një gjini në rritje të një sipërfaqeje që rezulton. (Shih seksionin Përgjithësimet më poshtë.) Një deklaratë më e thjeshtë e teoremës përdor teorinë e grafit. Grupi i rajoneve të një harte mund të përfaqësohet në mënyrë më abstrakte si një graf i padrejtuar që ka një kulm për çdo rajon dhe një skaj për çdo çift rajonesh që ndajnë një segment kufitar. Ky grafik është planar: ai mund të vizatohet në rrafsh pa kryqëzime duke vendosur çdo kulm në një vend të zgjedhur arbitrarisht brenda rajonit të cilit i përgjigjet, dhe duke vizatuar skajet si kthesa pa kryqëzime që çojnë nga kulmi i një rajoni, përgjatë një kulmi të përbashkët. segmenti kufitar, në kulmin e një rajoni ngjitur. Në të kundërt çdo grafik planar mund të formohet nga një hartë në këtë mënyrë. Në terminologjinë e teorisë së grafit, teorema me katër ngjyra thotë se kulmet e çdo grafi planar mund të ngjyrosen me maksimum katër ngjyra, në mënyrë që asnjë kulm fqinj të mos marrë të njëjtën ngjyrë, ose shkurt:"Çdo grafik planar është me katër ngjyra."