Ust sinir bulmak cok zor degilmis. Elimizde herhangi bir harita olsun. Ne kadar basit ya da ne kadar komplike oldugu onemli degil. Istedigimiz bir haritayi alalim.
Teorem: Hangi haritayi almis olursak olalim, bu haritayi sadece (ya da en fazla) alti renk kullanarak boyayabiliriz. Yedinci bir renge ihtiyacimiz yok.
Kanit: Baslamadan once: Eger elimizde sadece bir tane bolge olmus olsaydi, o zaman sadece bir renge ihtiyacimiz olacakti. Diger bes rengi kullanmayacaktik bile.
Oncelikle islemleri biraz daha kolaylastirmak icin sunu yapalim: Haritadaki her bolge icin o bolgenin ortasina bir nokta yerlestirelim. Eger iki bolge birbirine komsuysa, bu bolgelerin icine yerlestirdigimiz noktalarin arasina bir cizgi cizelim. Yalniz su kosula dikkat edelim: Iki nokta arasina cizdigim cizgi sadece bu iki bolge icinden gecsin, araya parazit bolge girmesin. Simdi elimizde bazi noktalar ve cizgiler var. Bundan sonra nokta yerine kose, cizgi yerine de kenar diyelim. Ozet gecelim: Iki kose arasinda bir kenar var demek tam olarak bu koselerin icinde bulundugu bolgeler arasinda bir sinir var demek. Bir baska deyisle, iki kose birbirine komsu demek bu koselerin icinde bulundugu bolgeler birbirine komsu demek. Daha once duyduysaniz, dual graftan bahsediyorum sadece.
Haritayi boyamak, yani bolgeleri boyamak demek ise her koseye bir renk vermek demek. Komsu bolgelerin ayni renge sahip olamamasi kosulu da arasinda kenar olan koselerin ayni renge sahip olamamasi kosuluna donustu.
Bundan sonra haritayi unutup sadece bu iskelete odaklanalim. Elimizde noktalar, kenarlar ve yuzler var. Yuz dedigimiz sey koseler ve kenarlar tarafindan sinirlandirilmis kapali alan. Bir de en disarida kalan, haritanin disi dedigimiz bir tane daha yuz var.
Simdi sunu gozlemleyelim: Hicbir kenar birbirini kesmiyor, birbirinin uzerinden gecmiyor. Cunku yukarida belirttigimiz gibi iki nokta arasinda cizdigimiz cizgi sadece bu iki noktanin icinde bulundugu bolgelerden geciyor. Yani teknik deyisle elimizde bir duzlemsel cizge (planar graph) var. Yani (disaridaki kocaman bolgeyi de bir bolge sayarsak) elimizde
koseler - kenarlar + yuzler = 2
esitligi var. Bu formul, Euler formulu olarak da biliniyor. Eger bir cizgeyi duzleme kenarlar birbirini kesmeyecek sekilde cizebiliyorsak, koseler - kenarlar + bolgeler = 2 esitligi saglanmak zorunda.
Bundan sonra bir gozlem daha yapmamiz gerekiyor: Her yuz en az uc tane kenara sahip olmak zorunda. Eger tek bir kose olsaydi bir yuz elde edemezdik, bir kenar bile elde edemezdik. Her iki tane kose olsaydi, bir kenar elde edebilirdik ama bir yuz elde edemezdik.
Bu son gozlemi ve Euler formulunu kullanarak sunu gosterebiliriz:
Derecesi 6'dan kucuk olan en az bir kose vardir. (Yani, hangi haritayi almis olursak olalim, oyle bir bolge vardir ki 5 ya da 5'ten az sayida komsusu vardir.). Ya da baska deyisle butun koselerin derecesi 6 ya da 6'dan buyuk olamaz.
Bu son yazdigimizi kanitlamadik, ama dogru oldugunu varsayalim. Yani derecesi 6'dan kucuk bir kose oldugunu varsayalim. K kosesi boyle bir kose olsun. Simdi K kosesini ve K kosesine ait butun kenarlari silelim. Elimizde kalan yeni cizgede orijinal cizgeden bir eksik kose var. Tumevarim kullanarak, bu bir eksiltilmis cizgenin alti renge boyandigini varsayarsak, K kosesinin en fazla 5 tane kosesi oldugu icin, K kosesi bu butun komsulardan farkli bir renge boyanabilir. Bu da kaniti tumevarim yardimiyla bitirdigimiz anlamina gelir.
Yukaridaki Euler formulu ve derecesi 6'dan kucuk olan bir kose oldugu gercegi bir lise ogrencisine birkac saatte anlatilabilir. Demek ki bir lise ogrencisine 6 Renk Teoremi kanitlanabilir. Hatta birkac hafta icinde birkac kere bulusup, kucuk odevler vererek ogrencinin kaniti kendi kendine tamamlamasi saglanabilir.
6 Renk Teoremi bu kadar kolaymis, 5 Renk Teoremi de zor degil. Ama yazmak istemedim, cizerek anlatilabilir. Ama 4 Renk Teoremi zor. Hala bilgisayar destegi olmadan kanitlanamiyor.