چار رنگی قضیہ کہتا ہے کہ کسی بھی ہموار سطح پر بنائے گئے نقشے کو زیادہ سے زیادہ چار رنگوں سے اس طرح رنگا جا سکتا ہے کہ سرحد بانٹنے والے دو خطے ایک ہی رنگ کے نہ ہوں۔ جو علاقے صرف ایک نقطے پر ملتے ہوں وہ ایک رنگ رکھ سکتے ہیں۔ نقشہ کتنا ہی پیچیدہ کیوں نہ ہو، یہ بات درست رہتی ہے۔
Regions 1, 2, 3, 4 each border multiple others. The left (4) and right (4) regions share no border, so they can share a colour. Exactly 4 colours needed here.
فرانسس گتھری نے 1852 میں انگریزی counties کے نقشے کو رنگتے ہوئے یہ قیاس پیش کیا۔ اس نے دیکھا کہ چار رنگ ہمیشہ کافی معلوم ہوتے ہیں، مگر وہ اسے ثابت نہ کر سکا۔ 124 سال تک یہ مسئلہ ریاضی دانوں کو الجھاتا رہا۔ بہت سے غلط ثبوت شائع ہوئے اور رد کیے گئے۔ پانچ رنگ ہمیشہ کافی ہوتے ہیں، اور اسے planar graphs کے لیے اولر کے فارمولے کی مدد سے ہاتھ سے ثابت کیا جا سکتا ہے۔
The four colour theorem took 124 years from conjecture to proof. The 1976 proof was the first major theorem verified by computer.
1976 کا ثبوت Kenneth Appel اور Wolfgang Haken نے دیا، اور یہ کمپیوٹر سے ثابت ہونے والا پہلا بڑا قضیہ تھا۔ انہوں نے تمام ممکنہ نقشوں کو 1,936 configurations تک گھٹایا اور پھر کمپیوٹر سے 1,200 گھنٹوں سے زیادہ CPU وقت میں ہر ایک کی جانچ کرائی۔ بہت سے ریاضی دان ایسے ثبوت سے بے چین تھے جسے مکمل طور پر ہاتھ سے نہ دیکھا جا سکے۔ اگر کوئی مکمل انسانی قرأت والا ثبوت موجود ہے، تو ابھی تک دریافت نہیں ہوا۔
Five outer regions (an odd number) force the ring to use 3 colours: no 2-colouring of a 5-cycle exists. The centre region is adjacent to all five, touching all three ring colours, so it must be a fourth colour. This shows four is genuinely sometimes necessary.
ہر مستوی نقشہ زیادہ سے زیادہ چار رنگوں سے رنگا جا سکتا ہے تاکہ سرحد بانٹنے والے دو علاقے ایک ہی رنگ کے نہ ہوں۔ فرانسس گتھری نے 1852 میں یہ قیاس پیش کیا۔ Appel اور Haken نے 1976 میں 1,936 configurations کو کمپیوٹر سے verify کروا کر اسے ثابت کیا، یوں یہ کمپیوٹر کی مدد سے ثابت ہونے والا پہلا بڑا قضیہ بنا۔ 1997 میں Robertson، Sanders، Seymour اور Thomas نے اسے 633 configurations تک مختصر کیا۔ یہ قضیہ torus پر درست نہیں، جہاں کبھی سات رنگ درکار ہو سکتے ہیں۔