مبرهنة فيزينغ: درجة3 قد تحتاج ثلاثة ألوان للحواف أو أربعة

الخلاصة السريعة

لأن اختلاف ألوان الحواف عند كل رأس شرط محلي، لكن الاختيارات يجب أن تتوافق في الرسم كله. الكامل على أربعة رؤوس يقبل3 ألوان للحواف. أما رسمنا ذو الجسر VW فيربط جهتين من5 رؤوس، وكل رأس درجته3؛ ثلاثة ألوان كانت ستجبر كل لون على استعمال الجسر، وهو حافة واحدة بلون واحد فقط. لذلك يحتاج4، ولدينا تلوين صريح بها.

• نلون الحواف لا الرؤوس. كل حافتين تتلاقيان عند رأس تحتاجان لونين مختلفين؛ الحافتان المنفصلتان يجوز لهما اللون نفسه. الرسم بسيط غير موجه بلا حلقات ذاتية أو حواف مكررة.
• رأس درجته3 يمنع أقل من3 ألوان لحوافه المتلاقية. وبحسب فيزينغ،4 تكفي في الرسم البسيط ذي Δ=3. [1] [2] يبقى تحديد هل3 ممكنة، ولا يكفي النظر إلى درجة رأس واحد.
• الكامل على A وB وC وD له الحواف AB وAC وAD وBC وBD وCD. نجعل {AB,CD} أزرق و{AC,BD} أحمر و{AD,BC} ذهبًا؛ عند كل رأس لون من كل نوع، فيثبت أقل عدد3.
• في رسم العشرة نثبت S={A,B,C,D,V} وT={E,F,G,H,W}، وحافة واحدة بينهما VW. كل رأس درجته3. حذف VW يترك جهتين من خمسة، والعدد الفردي هو ما سنستعمله في البرهان.
• لو كفت3 ألوان، لظهر كل لون مرة عند كل رأس. داخل جهة من5 رؤوس، حافة اللون تغطي رأسين، فيبقى رأس يحتاج حافة عابرة. لا تعبر إلا VW؛ يحتاجها كل لون، وهذا مستحيل لحافة تحمل لونًا واحدًا.
• نعطي تلوينًا صحيحًا من4 ألوان ونتحقق من كل رأس. مع منع3 يثبت أقل عدد4. لا نلون طرفي الحافة بلونين كما في تلوين الرؤوس، ولا نعد عبور خطوط الصورة رأسًا جديدًا.

الحواف المتلاقية تحتاج ألوانًا مختلفة

الحافة AC تصل A بـC، وهي نفسها CA في رسمنا غير الموجه. إذا لاقتها AD عند A، فلا بد من اختلاف لونيهما. أما AC وBD فأطرافهما مختلفة، ويجوز أن يكون لونهما واحدًا دون مخالفة الشرط.

نكتب χ′(G) لأقل عدد من ألوان الحواف في تلوين صحيح. هذا مختلف عن χ(G) لألوان الرؤوس. الدرجة العظمى Δ(G) تعد أكبر عدد من الحواف عند رأس؛ لا نعد تقاطع خطوط الصفحة اتصالًا جديدًا.

عند رأس له3 حواف، تحتاج تلك الحواف إلى3 ألوان مختلفة، لذلك χ′(G)≥3. قد تفشل محاولة بثلاثة بسبب علاقة الأجزاء الأخرى ببعضها؛ الحد المحلي لا يعطينا دائمًا تلوينًا للرسم كله.

تضمن فيزينغ χ′(G)≤Δ(G)+1 للرسم البسيط. [2] ومع الحد الأدنى الذي تفرضه الحواف المتلاقية، نحصل على القيمتين Δ أوΔ+1. [1] مثالنا بدرجة عظمى3 يترك احتمال3 أو4 فقط.

نقصد رسمًا محدودًا بلا حلقات ذاتية أو حواف مكررة، ونلون كل حافة مرة. سنثبت حدًا أدنى بشاهد أو عائق، وحدًا أعلى بقائمة ألوان صالحة، بدل الاكتفاء بمحاولة توقفت في منتصف الرسم.

الكامل على أربعة يقبل ثلاثة ألوان للحواف

نثبت A وB وC وD، ونرسم AB وAC وAD وBC وBD وCD. كل رأس متصل بالثلاثة الآخرين، فدرجة كل واحد3. مجموع الحواف6، ولا نحول عدد الرؤوس4 إلى عدد لازم لألوان الحواف.

نختار الأزرق للحافتين AB وCD، والأحمر للحافتين AC وBD، والذهب للحافتين AD وBC. الحافتان داخل كل مجموعة لا تشتركان في رأس؛ إذن لا يظهر لون مرتين عند رأس واحد.

راجع A: AB زرقاء وAC حمراء وAD ذهبية. وراجع B: AB زرقاء وBD حمراء وBC ذهبية. ينطبق الأمر على C وD أيضًا؛ حواف كل رأس تحمل الألوان الثلاثة مختلفة.

هذا تلوين صالح بـ3 ألوان، فيثبت إمكان3. ودرجة الرأس3 تمنع أقل من3، فيكون χ′=3. الكامل على أربعة يحتاج4 ألوان للرؤوس لأن كل رأسين متجاوران، لكنه يحتاج3 للحواف في المثال نفسه.

اللوحة اليمنى من الصورة الرئيسية تعرض هذا التلوين. الحواف المتقاطعة في وسط الرسم قد تشترك في لون لأنها لا تتلاقى عند رأس مسمى؛ نقطة تقاطعها الهندسية ليست من A وB وC وD.

رسم من عشرة رؤوس مع جسر واحد

نثبت عشرة رؤوس A وB وC وD وV وE وF وG وH وW. جهة S={A,B,C,D,V} لها الحواف AC وAD وBC وBD وCD وAV وBV. لا توجد AB؛ يصل A بـV وV بـB بدلًا منها.

الجهة T={E,F,G,H,W} لها الحواف EG وEH وFG وFH وGH وEW وFW. لا توجد EF؛ يستعمل E وF الرأس W في الوصلات المبينة. الأسماء V وW رأسان مختلفان عن الأحرف الأخرى.

نضيف VW وحدها بين الجهتين. صار عدد الحواف15: سبع داخل S، وسبع داخل T، وحافة عابرة واحدة. لا توجد أي وصلة أخرى بين المجموعتين، وكل قوائم الحواف هنا نهائية لا مجرد أمثلة لبعض الاتصالات.

في S، عند A الحواف AC وAD وAV، وعند B الحواف BC وBD وBV، وعند C الحواف AC وBC وCD، وعند D الحواف AD وBD وCD، وعند V الحواف AV وBV وVW. كلها درجة3.

وفي T كذلك لكل رأس3 حواف؛ W له EW وFW وVW. الحافة VW جسر: حذفها يفصل الجهتين، لأن أي انتقال بينهما يحتاجها. يبقى داخل كل جهة خمس رؤوس، ويتصل رأسها الوسيط ببقية الجهة.

لماذا كان كل لون سيحتاج VW؟

افترض أن هناك تلوينًا صحيحًا بـ3 ألوان. عند كل رأس3 حواف، فتحتاج ثلاثة ألوان مختلفة. إذن كل واحد من الألوان الثلاثة يظهر مرة عند كل رأس؛ لا يكفي أن يظهر في معظم الرؤوس.

ثبت لونًا واحدًا وانظر إلى الرؤوس الخمسة في S. الحواف بهذا اللون لا تتلاقى عند رأس، ولكل رأس منها حافة واحدة. كل حافة داخلية تغطي اثنين من رؤوس S، والحافة العابرة تغطي واحدًا من S وواحدًا من T.

إذا لم يستعمل اللون VW، فلن توجد له أي حافة عابرة من S. ستكون الرؤوس الخمسة مغطاة بحواف داخلية، وكل واحدة تغطي رأسين، فيلزم أن يكون5 مساويًا لعدد زوجي. هذا مستحيل.

نكتب الحساب 5=2a+b، حيث a عدد الحواف الداخلية بذلك اللون وb عدد الحواف العابرة. لا تتاح إلا VW، لذا b يساوي0 أو1؛ فردية5 تجبر b=1. هذه الحجة تخص كل لون على حدة.

إذن الأزرق يحتاج VW، والأحمر يحتاجها، والذهب يحتاجها أيضًا. لكن VW حافة واحدة لا نكررها ولا نعطيها ثلاثة ألوان. يتناقض ذلك مع التلوين المفترض، فلا يمكن تلوين هذا الرسم بثلاثة.

الصورة الداخلية تحذف VW وتعرض الجهتين كلًا وحدها. لا ندعي أن كل جسر في كل رسم يمنع3 ألوان؛ البرهان جمع درجة3 عند كل رأس مع جهتين فرديتين ووصلة واحدة. غياب إحدى هذه الفرضيات يحتاج فحصًا آخر.

تلوين بأربعة يثبت الحد الأعلى

نعود إلى الرسم الأصلي ذي الحواف15، بما فيها VW. نختار الأزرق لـAC وBD وEG وFH وVW، والأحمر لـAD وBC وEH وFG، والذهب لـCD وAV وGH وEW، والأخضر لـBV وFW.

داخل S، عند A الأزرق والأحمر والذهب، وعند B الأحمر والأزرق والأخضر، وعند C الأزرق والأحمر والذهب، وعند D الأحمر والأزرق والذهب، وعند V الذهب والأخضر والأزرق. لا لون يتكرر في حواف رأس واحد.

داخل T ينطبق فحص مماثل: E له الأزرق والأحمر والذهب، وF الأحمر والأزرق والأخضر، وG الأزرق والأحمر والذهب، وH الأحمر والأزرق والذهب، وW الذهب والأخضر والأزرق. استخدام أربعة ألوان في الرسم لا يفرض أربعة عند كل رأس.

الجدول يجمع الحواف بحسب اللون. المجاميع5 و4 و4 و2 تعطي15، والقوائم تغطي الحواف كلها مرة واحدة. يمكن مشاركة لون بين حواف منفصلة؛ لا نطالب بلون خاص لكل حافة من الخمس عشرة.

بقي أقل عدد أكبر من3 لأن البرهان السابق يمنع3، ولدينا الآن4 صالحة. إذن χ′=4. يتفق ذلك مع احتمال Δ+1 عند Δ=3؛ ليس مجرد أثر فشلنا في اختيار لون في محاولة سابقة.

ميز العائق المثبت من فشل محاولة اختيار

يمكن لخيار سيئ في بداية تلوين أن يترك حافة بلا لون مناسب مع بقاء حلول أخرى للرسم. لذلك لم نستعمل توقف محاولة دليلًا على استحالة3؛ أثبتنا أن أي تلوين بثلاثة سيجبر الحافة VW على حمل الألوان كلها.

في الرسم ذي درجة3 عند كل رأس، كل لون من ثلاثة كان سيشكل مطابقة كاملة: حواف لا تتلاقى وتغطي كل رأس مرة. فردية إحدى الجهتين تجبر حافة عابرة في كل مطابقة كهذه، وهو سبب العائق في مثالنا.

لا يمنع اللون الرابع مشاركة الرؤوس بين حواف من ألوان مختلفة؛ هذا الاشتراك متوقع عند رأس درجته3. كما لا يطلب التلوين مسارًا يزور الحواف كلها أو مطابقة واحدة تضم الحواف15.

المثلث ذو حواف متساوية اللون سؤال آخر، وتلوين الرؤوس سؤال آخر أيضًا. في صورنا الرؤوس رمادية، واللون للحافة. نراجع الحواف التي تلتقي عند كل دائرة مسماة، لا خطوطًا تتقاطع في الفراغ.

ثبت البساطة والدرجة العظمى، ثم اعرف الحدين المحتملين. لتحديد أقل عدد في الرسم المحدد، قدم تلوينًا صريحًا وسببًا يمنع عددًا أصغر. الكامل يحقق3، ورسم الجسر يحقق4، رغم أن درجات الرؤوس في الاثنين3.