teorema empat warna

lama tidak nulis di blog, para pecinta matematika. semester ini aku mendapt tugas untuk membuktikan teorema empat warna dalam mata kuliah teori graf. setelah mencari di internet ternyata pembuktiannya belum ada. sampai akhirnya aku membuktikannya menggunakan ilustrasi tapi ternyata teorema empat warna ini bisa dibuktikan dengan induksi matematika, seperti toerema 5 dan 6 warna. untuk itu terimajkasih untuk kelompok yang membuktikan teorema 5 dan 6 warna..
ini pembuktian teorema 4 warna

Jika G adalah graf planar, simple maka χ(G) ≤ 4

Bukti

Dengan menggunakan induksi matematika, n sebagai banyaknya simpul pada graf G

i)         Dibuktikan untuk n= 1, 2, 3, 4 benar

Pernyataan jelas benar untuk n=1, 2, 3, 4

ii)        Diasumsikan pernyataan benar untuk setiap graf simple, terhubung dan planar dengan simpul n-1 dimana n ≥ 5

Akan dibuktikan pernyataan benar untuk setiap graf dengan n simpul

·      Diketahui graf G  dengan n simpul

Maka G memuat suatu simpul dengan d(v) ≤ 4 (karena setiap graf planar memuat  setidaknya satu simpul v dengan d(v) ≤ 4)

Jika simpul v dihapuskan maka dihailkan graf planar H dengan |V(H)|= n-1

·   H graf planar dengan |V(H)|=n-1 maka berdasarkan asumsi setiap simpul dari graf G dapat di warnai dengan χ(G) ≤ 4

·   Selanjutnya v di kembalikan pada graf G

Terdapat 2 kemungkinan

Ø  d(v) < 4

karena v berikatan dengan 3 atau kurang dari 3 simpul dan ada 4 warna yang tersedia maka masih ada warna yang belum digunakan untuk member warna v.

Ø  d(v)=4

karena v berikatan dengan 4 simpul dan hanya ada 4 warna yang tersedia maka tidak ada warna yang tersisa untuk mewarnai v. untuk memberi warna pada v maka akan kita pandang simpul dua simpul (selain v) yang tidak saling berikatan tapi membentuk lintasan. Pewarnaan ini dapat diselesaikan sebagai berikut

v  jika kedua simpul tersebut tidak berikatan maka dapat diberi warna yang sama sehingga masih ada warna yang tersisa untuk member warna simul v.

v  apabila dua simpul tersebut membentuk lintasa maka simpul yang berada didalam tidak mungkin terhubung dengan simpul yang berada di luar lintasan. Sehingga simpul yang di dalam lintasan dan di luar lintasan dapat diberi warna yang sama. Sehingga masih  tersisa satu warna untuk member simpul v.

Jika untuk setiap  graf planar, simple dapat diwarnai dengan 4 atau kurang dari 4 (χ(G) ≤ 4)