ثلاثة رؤوس لكل مكون أحادي اللون: لماذا ينجح المثلث؟

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

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

• التلوين العنقودي بحد c يسمح باتفاق لون رأسين متجاورين، ويشترط ألا يزيد حجم كل مكون أحادي اللون على c رؤوس. [1] نثبت هنا c=3، ثم نبحث عن أقل عدد ألوان مستعملة. نعمل على رسم محدود وبسيط وغير موجه وغير فارغ الرؤوس. نلون الجميع، حتى المعزول، بأسماء ألوان قابلة للتبديل. الرقم 3 هنا حجم مكون، لا عدد ألوان مفروضًا.
• كل مكون نفحصه داخل الرؤوس ذات اللون نفسه وحوافها الأصلية. الحافتان المنفصلتان AB وCD تقبلان 1111 بأقل 1؛ فئة اللون حجمها 4 لكن المكونين حجمهما 2 و 2. المعزول مكون من رأس، والرسم بلا حواف يقبل 1 للجميع بأقل 1.
• P4 بالحواف AB BC CD يرفض 1111 لأن مكونه حجمه 4، ويقبل 1122 بأقل 2. المثلث يقبل 111 بأقل 1. التلوين الصحيح العادي يطلب اختلاف لون طرفي كل حافة، ويقلل عدد الألوان. [2] لذلك تكون مكوناته أحادية اللون رؤوسًا منفردة، فيحقق حد الثلاثة أيضًا. التلوين بعيب d يحد الدرجة القصوى داخل كل مكون أحادي اللون بالقيمة d. [3] حد حجم المكون ثلاثة يختلف عن حد الدرجة؛ المسار قد يطول مع بقاء درجته اثنين. العيب 1 يحقق حد الثلاثة لأن مكوناته حواف أو رؤوس؛ حد الثلاثة يحقق العيب 2، لكن P4 بلون واحد يثبت أن العيب 2 وحده لا يكفي.
• تقسيم الرؤوس إلى غابات يطلب أن تستحث كل فئة غابة، ويقلل عدد الفئات. [4] الغابة تمنع الدورة، لكنها قد تضم مكونًا كبيرًا؛ حد الثلاثة يسمح بمثلث صغير. المثلث يحتاج 1 لحد الثلاثة و 2 للغابات؛ P4 يحتاج 2 لحد الثلاثة و 1 للغابات. لذلك لا ترتيب ثابت بين العددين. النجمة بثلاث أوراق تحتاج 2، رغم أنها غابة، بالشاهد 1122.
• P5 وP6 وP7 تحتاج 2 بالشواهد 11122 و 111222 و 1112221؛ في P7 فئة اللون 1 تضم 4 رؤوس لكن مكوناتها 3 و 1. C4 وC5 وC6 تحتاج 2 بالشواهد 1122 و 11122 و 111222. النجمة بخمس أوراق تقبل 111222 بأقل 2؛ المركز وورقتان مكون 3، والأوراق الأخرى منفردة في اللون 2.
• K4 وK5 وK6 تحتاج 2 بالشواهد 1112 و 11122 و 111222. K7 تحتاج 3 بالشاهد 1112223؛ كل فئة في الكامل متصلة، فلا يتسع اللون الواحد لأكثر من 3. عمومًا K_n تحتاج سقف n/3. تقسيم أي رسم إلى مجموعات لا تتجاوز 3 يعطي هذا العدد حدًا أعلى، لكنه ليس شرطًا على حجم فئة اللون في كل رسم. K2,3 وK3,3 والماسة تحتاج 2.
• حصر 64 رسمًا رباعيًا أعطى 960 تقسيمًا: 922 تحقق حد الثلاثة، 337 صحيحة عاديًا، 902 غابات، 778 بعيب 1، 937 بعيب 2. بحث الأقل جرب 140 تعيينًا كاملًا: الأقل 1 في 26 رسمًا و 2 في 38. قل عن الصحيح في 44 وعن العيب 1 في 16؛ زاد عن العيب 2 في 15 وعن الغابات في 16، وقل عن الغابات في 4. فحص منفصل بحصر المكونات راجع 20 مثالًا و 64 رسمًا وقوائم تلوينات الأقل وأعداد البحث، ورسم رأس ورسمَي رأسين؛ مولد التقسيمات مشترك والأعداد ليست أزمنة أو مراجعة بشرية.

حد الثلاثة يخص المكون، لا فئة اللون كلها

التلوين العنقودي بحد c يسمح باتفاق لون رأسين متجاورين، ويشترط ألا يزيد حجم كل مكون أحادي اللون على c رؤوس. [1] نثبت هنا c=3، ثم نبحث عن أقل عدد ألوان مستعملة.

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

الاتصال المطلوب يسير داخل اللون نفسه. طريق يمر برأس من لون آخر لا يدمج مكونين أحاديي اللون، ولا نضيف حواف غير موجودة. المكونات المختلفة تستطيع حمل الاسم اللوني نفسه.

في الحافتين AB وCD بلا حواف أخرى، 1111 يجعل فئة واحدة ذات 4 رؤوس، لكنها تستحث مكونين: AB وCD، حجم كل منهما 2. ينجح بأقل 1. شرط أن يكون مجموع رؤوس اللون ثلاثة سيحكم خطأً على هذا المثال.

الرأس المعزول يبقى ملونًا ويشكل مكونًا منفردًا من حجم 1. الرسم ذو الرؤوس والخالي من الحواف يقبل اللون 1 للجميع؛ مكوناته كلها منفردة، وأقل عدد مستعمل 1 لا 0.

النطاق محدود وبسيط وغير موجه وبلا حلقات أو حواف مكررة أو أوزان، وله رأس واحد على الأقل. نلون الرؤوس، ونقلل عدد الأسماء المستعملة. تبديل أسماء الألوان لا يغير المكونات ولا نجاح الشرط.

المثلث 111 ينجح، والمسار 1111 يفشل

في المثلث ABC بالحواف AB AC BC، إعطاء الجميع اللون 1 ينتج مكونًا واحدًا من 3 رؤوس. ينجح الحد مع وجود الدورة؛ لم نشترط منعها. اللون الواحد يحقق أقل ممكن، فيثبت الأقل 1.

في P4 بالحواف AB BC CD، 1111 ينتج مكونًا واحدًا من 4 رؤوس، فيفشل. طول الطريق لا يكسر الاتصال، ولا يجعله مكونات أصغر تلقائيًا.

الشاهد 1122 على A B C D يصلحه: AB مكون اللون 1 بحجم 2، وCD مكون اللون 2 بحجم 2. الحافة BC بين لونين فلا تصل المكونين داخل لون واحد. ينجح بلونين، ورفض الواحد يثبت الأقل 2.

لا نحتاج تلوينًا صحيحًا لكل حافة؛ AB وCD أحاديتا اللون في الشاهد الناجح. لم نحذفهما من الرسم، بل بقيتا داخل مكونين صغيرين.

في النجمة AB AC AD، 1111 مكون حجمه 4 أيضًا، فيفشل. 1122 يجعل A وB مكونًا من 2، وC وD رأسين منفردين باللون 2، فينجح بأقل 2. مشاركة اللون لا تعني أن الورقتين متصلتان.

درجة أحادية اثنان لا تحد حجم المكون

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

التلوين بعيب d يحد الدرجة القصوى داخل كل مكون أحادي اللون بالقيمة d. [3] حد حجم المكون ثلاثة يختلف عن حد الدرجة؛ المسار قد يطول مع بقاء درجته اثنين.

إذا كان المكون الأحادي حجمه 3 على الأكثر، فكل رأس فيه له جارَان على الأكثر داخل ذلك اللون؛ الرسم بسيط. إذن كل تلوين يحقق حد الثلاثة يحقق العيب 2.

العكس يفشل: في P4 بلون واحد، درجتا الطرفين 1 ودرجتا الداخل 2، فيحقق العيب 2، لكن المكون حجمه 4 فيرفضه حد الثلاثة. تقييد عدد الجيران ليس تقييدًا لعدد الرؤوس المتصلة عبر سلسلة.

العيب 1 أقوى هنا: مكون متصل كل درجاته على الأكثر 1 لا يزيد على رأسين؛ إما رأس منفرد أو حافة. لذلك كل تلوين بعيب 1 يحقق حد الثلاثة، وأقل حد الثلاثة لا يزيد على أقل العيب 1.

المثلث 111 يبين الفرق: حجم 3 مقبول، لكن كل رأس له جاران موافقان، فيفشل العيب 1. وP3 مع معزول يقبل الجميع باللون 1 لحد الثلاثة؛ مكون الطريق 3 والمنفرد 1، رغم وجود رأس ذي جارَين موافقين.

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

منع الدورة وحد الحجم شرطان لا يرتبان العددين

تقسيم الرؤوس إلى غابات يطلب أن تستحث كل فئة غابة، ويقلل عدد الفئات. [4] الغابة تمنع الدورة، لكنها قد تضم مكونًا كبيرًا؛ حد الثلاثة يسمح بمثلث صغير.

المثلث يقبل 1 لحد الثلاثة، لكنه لا يقبل 1 لغابات اللون لأن اللون الواحد يستحث دورة. 112 يقسمه إلى حافة ورأس، فيحقق الغابات بأقل 2.

P4 يقبل 1111 لغابات اللون؛ فئته طريق بلا دورة، مهما زاد حجمها عن 3. لحد الثلاثة يحتاج 2 كما أثبتنا. إذن المثلث يجعل أقل الحد أصغر من الغابات، والمسار يجعله أكبر.

لا ترتيب ثابت بين الأقلين. السماح بحافة أحادية اللون مشترك بين السؤالين، لكنه لا يحدد ما الذي يسمح به بعد الحافة: مكون صغير قد يحوي دورة، وغابة قد تكون كبيرة.

في النجمة بخمس أوراق AB AC AD AE AF، 111222 على A B C D E F يجعل مكون اللون 1 هو A B C، حجمه 3. D وE وF لا تتصل فيما بينها فتشكل ثلاثة مكونات منفردة باللون 2.

الشاهد يثبت إمكان 2؛ الرسم كله متصل وله 6 رؤوس، فاللون الواحد يفشل حد الحجم، فيثبت الأقل 2. مع ذلك اللون الواحد يصلح لغابات اللون لأنها شجرة. لا نعد فئة اللون 2 مكونًا من 3 لمجرد أن عدد رؤوسها 3.

P7 يعيد اللون 1 بعد فاصل من اللون 2

P5 وP6 وP7 مسارات على الرؤوس بالترتيب. الشواهد 11122 و 111222 و 1112221 تقطع الرؤوس إلى كتل أحادية اللون من أحجام لا تزيد على 3. كلها متصلة أصلًا وأحجامها أكبر من 3، فيفشل الواحد وينجح الاثنان، فيثبت الأقل 2.

في P7، رؤوس اللون 1 هي A B C وG؛ عددها 4. لكنها تستحث مكون ABC من 3 ورأس G منفردًا. بين C وG توجد رؤوس D E F من اللون 2، فلا يصلها طريق أحادي اللون 1.

في C4 بالحواف AB BC CD AD، 1122 يعطي المكونين AB وCD من 2. حافة الإغلاق AD بين لونين، فتظل المكونات منفصلة. اللون الواحد يستحث الدورة كلها من 4 فيفشل؛ الأقل 2.

في C5، 11122 يعطي ABC من 3 وDE من 2؛ الحافتان CD وAE تعبران بين اللونين. وفي C6، 111222 يعطي ABC وDEF من 3، وحافتا الفصل CD وAF مختلفتا اللون. الأقل 2 في كلتيهما لأن الأصل متصل وأكبر من 3.

الدورة ليست ممنوعة لذاتها. المثلث دورة ناجحة بلون واحد؛ الدورات الأطول تفشل بلون واحد بسبب حجم المكون. نجاح لونين لا يتطلب التناوب عند كل حافة، كما تبين الكتل 111.

في K2,3 وK3,3، لون كل جانب بلون مستقل، بالشاهد 11222 أو 111222. لا حواف داخل أي جانب، فكل رأس فيه مكون منفرد؛ الأصل متصل وحجمه 5 أو 6، فيمنع الواحد ويثبت الأقل 2.

الماسة AB AC AD BC BD تقبل 1112؛ ABC مثلث أحادي من 3، وD منفرد باللون 2. الأصل متصل من 4 فيمنع الواحد؛ الأقل 2. المثلث لا يفسد الشاهد ما دام حجمه لا يتجاوز الحد.

في الكامل فقط تصبح فئة اللون مكونًا واحدًا

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

K4 وK5 وK6 تقبل 1112 و 11122 و 111222 بأقل 2. اللون الواحد يفشل لأنها متصلة وأكبر من 3، والشواهد تقسمها إلى فئات لا يتجاوز حجم أي منها 3، ومنها مثلثات مقبولة.

K7 تحتاج 3: لونان لا يغطيان أكثر من 6 رؤوس حين تسع كل فئة 3، فيستحيلان. 1112223 يعطي فئتين من 3 ورأسًا منفردًا، فينجح بثلاثة ويثبت الأقل.

عمومًا الأقل في K_n هو سقف n/3: إذا استعملنا k ألوان غطينا على الأكثر 3k رؤوس، فيلزم k≥⌈n/3⌉؛ وتقسيم الرؤوس إلى مجموعات من 3 مع مجموعة أخيرة أصغر يحقق الحد. ينطبق ذلك أيضًا على رأس واحد.

لأي رسم بسيط على n رؤوس، أعط كل مجموعة من ثلاثة على الأكثر لونًا خاصًا؛ أي مكون داخلها لا يتجاوز المجموعة، فينتج حد أعلى سقف n/3. الحواف التي تربط مجموعات مختلفة لا تؤثر في مكون لون واحد.

هذا البناء كافٍ، لكنه ليس شرطًا على فئات كل تلوين ناجح. الحافتان المنفصلتان وP7 يسمحان بفئة من 4 لأنها موزعة على مكونات صغيرة. لا تنقل مساواة الفئة بالمكون من الكامل إلى كل الرسوم.

كذلك لا تعني عبارة ثلاثة ألوان في عنوان بحث أن حجم المكون ثابت بثلاثة. تعريف المصدر يستخدم c لحد الحجم؛ اختيار c=3 وتقليل الألوان هنا هو سؤال الأمثلة، ولا ننقل إليه نتائج عامة عن عدد ألوان فئات رسوم أخرى.

ستة وعشرون رسمًا رباعيًا يقبل اللون الواحد

ثبتنا A B C D والحواف الست المحتملة AB AC AD BC BD CD. الإبقاء أو الحذف يعطي 2^6=64 رسمًا مسمى. حصر 15 تقسيمًا للرؤوس في كل رسم، مع تجاهل إعادة أسماء الألوان، يعطي 960 تقسيمًا.

نجح 922 لحد الثلاثة، 337 للتلوين الصحيح، 902 لغابات اللون، 778 للعيب 1، 937 للعيب 2. بحث الأقل بزيادة الألوان جرب 140 تعيينًا كاملًا حتى أول نجاح في كل رسم؛ هذه أعداد تعيينات وليست أزمنة تنفيذ.

اللون الواحد ينجح إذا وفقط إذا كانت كل مكونات الرسم الأصلي ذات 3 رؤوس على الأكثر. على أربعة رؤوس يحدث ذلك في الرسوم غير المتصلة: الخالي، وست حواف منفردة، وثلاث مطابقات بحافتين، واثني عشر P3 مع معزول، وأربعة مثلثات مع معزول؛ المجموع 26.

الرسوم المتصلة الثمانية والثلاثون تفشل بالواحد لأن مكونها من 4. تقسيم الرؤوس إلى زوجين بلونين ينجح مهما كانت الحواف، فتحتاج 2. هذا برهان العددين 26 و 38، وليس حكمًا عامًا على الرسوم المتصلة الأكبر.

قل الأقل عن الصحيح في 44 رسمًا، وعن العيب 1 في 16: اثنا عشر P3 مع معزول وأربعة مثلثات مع معزول. زاد عن العيب 2 في 15: اثنا عشر P4 وثلاث C4؛ درجتها القصوى 2 فتقبل الواحد للعيب 2، لكن اتصال الأربعة يمنعه لحد الحجم.

زاد عن الغابات في 16 شجرة رباعية: اثنا عشر P4 وأربع نجمات بثلاث أوراق. وقل عن الغابات في 4 مثلثات مع معزول؛ تحتاج الغابات 2 ويكفيها 1 لحد الثلاثة. يظهر الاتجاهان داخل الحصر نفسه.

فحص أول جمع رؤوس المكونات الأحادية بدمج المجموعات المتصلة عبر الحواف، ثم قاس حجم كل مجموعة. فحص منفصل بدأ من كل رأس لم يُزَر بعد وتوسع إلى جيرانه ذوي اللون نفسه، ثم رفض المكون إذا تجاوز 3. لم يكتف بقياس الدرجة أو بمنع الدورة.

اتفق الفحصان في 20 مثالًا و 64 رسمًا، وكل قوائم تلوينات الأقل وأعداد البحث والشاهد الأول. راجعنا رأسًا واحدًا ورسمَي رأسين بحافة وبدونها. مولد تقسيمات الألوان مشترك، والمقارنات الأخرى أعيد حسابها؛ لا ندعي مراجعًا مستقلًا بالكامل أو مراجعة بشرية.

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