مبرهنة بروكس: حد الدرجة لا يساوي دائمًا عدد الألوان اللازم

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

لأن «تكفي ثلاثة» تسمح بأن يكفي اثنان فعلًا. في الرسم الثنائي الكامل بين {A,B,C} و{D,E,F}، الدرجة العظمى3 لكن لونين يكفيان، ولا يكفي لون واحد. أما الرسم الكامل على A وB وC وD فدرجته العظمى3 ويحتاج4 ألوان، لأنه من الاستثناءات. نلون الرؤوس، ويجب اختلاف لون طرفي كل حافة.

• العدد اللوني χ(G) هو أقل عدد ألوان لتلوين الرؤوس بحيث يختلف لون كل رأسين متصلين بحافة. [2] الدرجة العظمى Δ(G) هي أكبر عدد من الحواف عند رأس واحد؛ ليست أقل درجة أو عدد الرؤوس.
• دورة A→B→C→D→E→A لها Δ=2، لكنها تحتاج3 ألوان؛ التناوب بلونين يفشل عند الإغلاق. أما دورة A→B→C→D→E→F→A فلها Δ=2 ويكفيها لونان متناوبان. الدورة الفردية استثناء، والزوجية ليست كذلك.
• في الرسم الكامل على A وB وC وD، تتصل كل رأسين مختلفين. الدرجة العظمى3، ولا يمكن أن يشترك رأسان في لون؛ لذلك العدد الأدنى4. لا نستعمل حد بروكس دون فحص استثناء الرسم الكامل.
• في الرسم الثنائي الكامل بين {A,B,C} و{D,E,F}، درجة كل رأس3. أعط المجموعة الأولى لونًا والثانية لونًا آخر؛ كل حافة تعبر بينهما، فيصح التلوين بلونين. حافة موجودة تمنع لونًا واحدًا، فيكون χ=2<3.
• شرط الاتصال مهم. [2] إذا رسمنا الكامل على A وB وC وD وتركنا E وF معزولين، بقيت Δ=3 لكن χ=4. الرسم كله ليس كاملًا ولا دورة فردية، ومع ذلك مكونه الكامل يفرض أربعة ألوان.
• تلوين صحيح بخمسة ألوان لا يثبت أن خمسة لازمة؛ ابحث عن حد أدنى وشاهد يبلغه. كذلك لا تقارن تلوين الرؤوس بتلوين الحواف أو المثلث الأحادي اللون؛ هنا لون الخط لا يدخل قاعدة اختلاف الجيران.

ميز العدد الأدنى من الحد الذي يكفي

نعمل على رسم بسيط غير موجه: لا حافة من الرأس بنفسه ولا حافتان مكررتان بين الاسمين نفسيهما. التلوين يخص الدوائر المسماة، ويمنع لونًا واحدًا لطرفي حافة موجودة. لا يشترط اختلاف كل الرؤوس عندما لا تتصل بحافة.

العدد اللوني هو أقل عدد ألوان يحقق اختلاف الجيران. [2] إذا أعطينا كل رأس لونًا خاصًا وجدنا تلوينًا، لكنه قد يستعمل ألوانًا أكثر من اللازم. إثبات الحد الأدنى يحتاج سببًا يمنع عددًا أصغر وشاهدًا بالعدد المطلوب.

نكتب Δ(G) للدرجة العظمى؛ احسب عدد الحواف المتصلة بكل رأس ثم خذ الأكبر. ونكتب χ(G) للعدد اللوني. علامة χ(G)≤Δ(G) تعني وجود تلوين لا يزيد عدد ألوانه على الحد، ولا تفرض المساواة.

في صيغة بروكس التي نستخدمها، نثبت اتصال الرسم ونستبعد الرسم الكامل والدورة الفردية. [2] أمثلتنا الأربعة الأولى متصلة فعلًا. سنعرض لاحقًا لماذا حذف شرط الاتصال من العبارة قد يعطي استنتاجًا خاطئًا.

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

التناوب ينجح على ستة ويفشل على خمسة

ابدأ بالحواف AB وBC وCD وDE وAE فقط على A وB وC وD وE. كل رأس له جاران، فدرجته2 والدرجة العظمى2. هذه دورة فردية؛ العدد خمسة يصف رؤوس الدورة، لا عدد الألوان.

لو استعملنا لونين فقط وبدأنا A بالأزرق، لزم B أحمر وC أزرق وD أحمر وE أزرق. الحافة AE تصل رأسين أزرقين، فيفشل التلوين عند الإغلاق. البدء بالأحمر يبدل الأسماء ولا يصلح هذا التعارض.

إذن لا يكفي لونان. نعطي A أزرق وB أحمر وC أزرق وD أحمر وE ذهبًا. كل حافة تصل لونين مختلفين، فيكفي3. يجتمع منع الاثنين مع شاهد الثلاثة لإثبات χ=3، رغم Δ=2.

الآن أضف رأس F إلى قائمة دورة جديدة: AB وBC وCD وDE وEF وAF. الدرجة العظمى2 أيضًا. التلوين A أزرق وB أحمر وC أزرق وD أحمر وE أزرق وF أحمر يختلف على الحواف الست، بما فيها AF.

وجود حافة يمنع لونًا واحدًا، وشاهد اللونين يثبت χ=2. الصورتان الرئيسيتان لا تعرضان فشل بروكس؛ الدورة الفردية أحد الاستثناءات المعلنة، بينما الدورة الزوجية تحقق الحد2.

الكامل على أربعة يحتاج أربعة ألوان

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

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

نعطي A أزرق وB أحمر وC ذهبًا وD أخضر. كل زوج مختلف اللون، لذلك كل الحواف الست صحيحة، وتكفي4 ألوان. النتيجة χ=4 وΔ=3؛ لدينا حد أدنى4 وشاهد يبلغه.

هذا الرسم كامل، فهو من الاستثناءات؛ الكامل والدورة الفردية يحتاجان Δ+1 لونًا في صيغة المبرهنة. [1] لا ننقل حكم «تكفي الدرجة العظمى» إليه بعد تجاهل الاستثناء.

اللوحة اليسرى من الصورة الداخلية تعرض الرؤوس الأربعة بأربعة ألوان. تقاطع الحافتين في وسط اللوحة لا يدخل في حساب الرؤوس أو الجيران، لأن نقطة التقاطع ليست دائرة مسماة.

درجة عظمى3، لكن العدد اللوني2

نثبت ستة رؤوس، ونقسمها إلى L={A,B,C} وR={D,E,F}. نصل كل رأس من L بكل رأس من R فقط. الحواف AD وAE وAF وBD وBE وBF وCD وCE وCF؛ لا حافة داخل أي مجموعة.

كل رأس يتصل بثلاثة من الجهة الأخرى، فتكون الدرجات(3,3,3,3,3,3) والدرجة العظمى3. والرسم متصل: من أي رأس يساري نصل مباشرة إلى أي يميني، وإلى يساري آخر عبر رأس يميني.

نعطي A وB وC اللون الأزرق، وD وE وF اللون الأحمر. كل حافة تصل الأزرق بالأحمر، لذلك التلوين صحيح بلونين. تكرار الأزرق داخل L جائز لأن أعضاءها لا تتصل فيما بينها.

لا يكفي لون واحد لأن AD حافة موجودة، فيجب أن يختلف طرفاها. شاهد اللونين مع هذا المنع يثبت χ=2. إذن χ=2<3 رغم أن حد بروكس يسمح باستعمال3 ألوان.

يمكن صنع تلوين صحيح بثلاثة ألوان أيضًا: أعط A لونًا ثالثًا واترك البقية كما كانت. ما زال كل جار لـA أحمر، فيصح التلوين. هذا لا يجعل3 هو العدد الأدنى؛ لدينا بالفعل تلوين صحيح باثنين.

الرؤوس المعزولة لا تلغي حاجة المكون الكامل

نبني مثالًا خامسًا على A وB وC وD وE وF: الحواف الست للكامل على A وB وC وD فقط، وE وF معزولان. الدرجات(3,3,3,3,0,0)، والدرجة العظمى3.

الرسم غير متصل؛ لا طريق من E إلى A ولا من F إلى أي رأس آخر. كما أن الرسم كله ليس كاملًا على الستة، ولا دورة فردية. رغم ذلك تفرض الرؤوس الأربعة المتصلة ببعضها4 ألوان كما أثبتنا.

يمكن إعطاء E وF اللون الأزرق نفسه المستخدم عند A، لأنهما بلا جيران. لذلك لا يرتفع العدد الأدنى إلى6؛ يبقى χ=4. إضافة رؤوس معزولة لم تزل حواف المكون الكامل التي تمنع مشاركة الألوان فيه.

هذا شاهد على خطأ حذف شرط الاتصال ثم الاقتصار على سؤال هل الرسم كله كامل أو دورة فردية. لا نستعمل صيغة بروكس للمثال الخامس؛ نفحصه مباشرة من مكونه الكامل وتلوين معزوليه.

الجدول يقارن خمس حالات: أربع رسوم متصلة معروضة في الصور، ثم المثال غير المتصل. اكتب الدرجة العظمى والعدد الأدنى كلًا في عموده؛ عدد الألوان في صورة ناجحة لا يكفي وحده لإثبات الأمثلية.

افحص صحة التلوين ثم أثبت أمثلية العدد

ابدأ بقائمة الحواف. لكل حافة قارن لوني الطرفين؛ اختلافهما يجعلها صالحة. بعد ذلك عد الألوان المستخدمة فعليًا، لا حجم مجموعة الألوان المسموح بها إذا تركنا بعضها دون استعمال.

في الدورة الزوجية، شاهد اللونين يمنع الحاجة إلى3، والحافة الموجودة تمنع النزول إلى1. وفي الكامل على أربعة، اختلاف كل زوج يمنع أقل من4. كل حد أدنى يعتمد على اتصالات الرسم، لا مجرد ألوان اخترناها في اللوحة.

في الرسم الثنائي الكامل، تلوين بثلاثة ألوان قد يكون صحيحًا لكنه غير أمثل. فرّق بين «وجدت تلوينًا صالحًا» و«أثبتُّ أقل عدد». المتباينة التي تعطي حدًا كافيًا لا تلزم بأن يصل كل رسم إلى ذلك الحد.

نلون الرؤوس هنا، لا الحواف. سؤال إيجاد مثلث حوافه بلون واحد في رسم كامل مختلف؛ الخطوط الرمادية في صورنا لا تحتاج تغيير ألوانها حتى يكون تلوين الرؤوس صحيحًا.

كذلك لا يضمن شرط الدرجة نمطًا هندسيًا أو أطوالًا أو رسمًا دون تقاطع. راجع البساطة والاتصال والاستثناءات، ثم استخدم الحد ضمن نطاقه. وعند تحديد العدد الأدنى، قدم شاهدًا وسببًا يستبعد الأعداد الأصغر.