مبرهنة مانتل: تسع حواف لا تحسم وجود مثلث على ستة رؤوس

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

لأن مبرهنة مانتل تعطي حدًا أعلى للرسم الخالي من المثلثات، ولا تقول إن كل رسم تحت الحد خالٍ منها. على ستة رؤوس، الرسم الثنائي الكامل بين {A,B,C} و{D,E,F} له9 حواف بلا مثلث. احذف CF وأضف AB؛ يبقى العدد9، لكن ABD وABE وABF تصبح مثلثات. أما10 حواف فتتجاوز الحد وتضمن وجود مثلث.

• نثبت ستة رؤوس مختلفة A وB وC وD وE وF، ورسمًا بسيطًا غير موجه بلا حواف مكررة أو حلقات ذاتية. المثلث ثلاثة رؤوس مع حوافها الثلاث؛ تقاطع الخطوط في الصفحة ليس رأسًا جديدًا.
• الرسم بين L={A,B,C} وR={D,E,F} يصل كل يساري بكل يميني فقط. حوافه AD وAE وAF وBD وBE وBF وCD وCE وCF؛ عددها3×3=9، ولا مثلث لأن أي ثلاثة رؤوس تضم اثنين من الجهة نفسها دون حافة بينهما.
• نحذف CF ونضيف AB، فتبقى9 حواف. الحواف AB وAD وBD تعطي ABD، وبالمثل نجد ABE وABF. ثبات عدد الحواف لا يعني ثبات وجود المثلث.
• إذا عدنا إلى الرسم الأصلي وأضفنا AB دون حذف، صار العدد10. يتجاوز هذا حد9، فتضمن مانتل وجود مثلث. [1] في رسمنا نستطيع تسميته مباشرة: ABD؛ الإضافة لا تزعم أن كل ثلاثية مثلث.
• تقسيم الستة إلى مجموعتين من رأسين وأربعة يعطي رسمًا ثنائيًا كاملًا بـ2×4=8 حواف، دون مثلث أيضًا. إذن غياب المثلث لا يفرض الوصول إلى العدد الأقصى9، والتوازن يحقق عددًا أكبر في المقارنة.
• إذا عرفت أن الرسم خالٍ من المثلثات، استنتج m≤9 عند n=6. وإذا عرفت m≥10، استنتج وجود مثلث. أما m≤9 وحدها فلا تحسم؛ افحص الاتصالات نفسها، ولا تستبدل العدد الكلي بأقل درجة أو بالمطابقة.

ثبت نوع الرسم قبل حساب الحد

نعمل على ستة رؤوس مختلفة A وB وC وD وE وF. الحافة AD تصل رأسين بلا اتجاه، ولذلك DA هي الحافة نفسها. لا نعد اتصال الرأس بنفسه، ولا نكرر الحافة في القائمة؛ هذه شروط الرسم البسيط هنا.

المثلث ABD يعني وجود AB وAD وBD جميعًا. لا يكفي طريق A→D→B ما لم توجد AB لإغلاقه. وجود رأس آخر قريب من خطوطه أو تقاطع خطين لا يمنحنا حافة ناقصة.

نكتب n لعدد الرؤوس وm لعدد الحواف. حد مانتل للرسم الخالي من المثلثات هو m≤⌊n²/4⌋؛ والرمز ⌊x⌋ يأخذ أكبر عدد صحيح لا يتجاوز x. [1] في مثالنا 6²/4=9، فلا تقريب يغير النتيجة.

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

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

مجموعتان من ثلاثة تحققان تسع حواف دون مثلث

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

لكل رأس من اليسار ثلاثة اختيارات يمينية، فيكون المجموع3×3=9 حواف مختلفة. لا نضاعف الرقم عند العد من جهة اليمين؛ الحافة الواحدة ليست عنصرًا جديدًا لأننا قرأناها من الطرف الآخر.

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

مثلًا ABD تملك AD وBD لكن AB غير موجودة. والثلاثية ADE تملك AD وAE لكن DE غير موجودة. غياب المثلث ليس ملاحظة عن شكل الصورة؛ حجة وجود رأسين من جهة واحدة تغطي جميع الثلاثيات.

بلغ هذا الرسم العدد9 دون مثلث. بذلك لا نستطيع تخفيض أكبر عدد ممكن على ستة رؤوس إلى8؛ لدينا شاهد يحقق9، والمبرهنة تمنع تجاوز9 مع الحفاظ على غياب المثلث. [1] اللوحة اليسرى من الصورة الرئيسية تعرض الحواف التسع كاملة.

غير حافتين مع بقاء العدد تسعة

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

الآن AB وAD وBD موجودة، فتشكل ABD. وبالطريقة نفسها AB وAE وBE تشكل ABE، وAB وAF وBF تشكل ABF. المثلثات الثلاث تشترك في AB، لكن كل واحدة قائمة صحيحة من ثلاثة رؤوس مختلفة.

حذف CF لا يمس هذه الشواهد، لأنها لا تستخدم C أصلًا. لذلك لا يعوض حذف حافة بعيدة أثر إضافة AB. قد يحافظ التبديل على العدد الكلي دون أن يحافظ على خاصية كانت سببًا في تنظيم الرسم الأول.

درجات A وB وC وD وE وF صارت(4,4,2,3,3,2)، بعد أن كانت(3,3,3,3,3,3). مجموع الدرجات ما زال18، لأن الحواف ما زالت9، لكن اتصال AB بين رأسي المجموعة اليسرى غيّر شكل الثلاثيات.

اللوحة اليمنى الرئيسية تعرض الرسم المعدل، وتبرز AB وAD وBD بالذهب. CF غير مرسومة لأنها محذوفة. بقية الاتصالات الرمادية موجودة؛ اللون لا يعني حذفها أو استبعادها من البحث عن مثلثات أخرى.

أضف AB بلا حذف: عشر حواف تتجاوز الحد

نبدأ مرة أخرى بالرسم الثنائي الأصلي ذي الحواف التسع، ثم نضيف AB دون حذف CF أو غيرها. يصبح العدد10. هذا رسم ثالث، فلا نخلطه بالرسم السابق الذي كان قد فقد CF.

في نطاق مانتل، تجاوز حد9 عند ستة رؤوس يجبر وجود مثلث. [1] وبما أن العدد صحيح، فأول عدد يتجاوز9 هو10. لا تحتاج النتيجة العامة إلى معرفة مواضع الحواف العشر حتى تضمن مثلثًا ما.

أما في مثالنا فنملك شاهدًا صريحًا: ABD حوافه AB وAD وBD. يوجد أيضًا ABE وABF، كما في الرسم المعدل السابق. إبقاء CF لا يلغي المثلثات، لأنها كلها تتكون من حواف ما زالت موجودة.

قد يزيد رسم آخر ذو10 حواف عدد المثلثات أو يغير أسماءها. الضمان يتعلق بوجود مثلث، ولا يحدد من العدد وحده أن ABD سيكون الشاهد في كل رسم أو أن المثلثات ستكون ثلاثة بالضبط.

اللوحة اليسرى من الصورة الداخلية تبقي CF وتعرض AB المضافة. افصل عملية الإضافة عن عملية الاستبدال: في الأولى يزيد العدد1، وفي الثانية حذف واحد وإضافة واحد يحفظان العدد.

مجموعتان غير متوازنتين تعطيان ثماني حواف

نبني الرسم الرابع بتقسيم مختلف للرؤوس الستة: مجموعة {A,B} ومجموعة {C,D,E,F}. نصل كل رأس في المجموعة الأولى بكل رأس في الثانية فقط. الحواف هي AC وAD وAE وAF وBC وBD وBE وBF.

عددها2×4=8. لا حافة بين A وB، ولا بين أي رأسين من C وD وE وF. تنطبق حجة وجود رأسين من الجهة نفسها على أي ثلاثية، فلا يوجد مثلث رغم اختلاف التقسيم وعدد الحواف.

درجتا A وB تساويان4، ودرجات C وD وE وF تساوي2. إذن الدرجات(4,4,2,2,2,2)، ومجموعها16، مطابق لضعف عدد الحواف8. مقارنة المجموع لا تغير حقيقة أن المجموعتين لا تملكان حواف داخلية.

في الرسم الثنائي الكامل على ستة رؤوس، تقسيم1 و5 يعطي5 حواف، وتقسيم2 و4 يعطي8، وتقسيم3 و3 يعطي9. هذه الحسابات تفسر لماذا حقق تقسيمنا المتوازن العدد الأكبر بين التقسيمات المعروضة، ولا تقول إن كل رسم خالٍ من المثلثات يجب أن يملك9.

الجدول يقارن الأمثلة الأربعة بأعدادها وشواهدها. واللوحة اليمنى الداخلية تعرض تقسيم2 و4 مع الحواف الثماني كلها. وجود عدد أقل من الحد يسمح بغياب المثلث، لكنه لا يثبت غيابه في رسم آخر بمجرد الرقم.

اقرأ جهة الاستنتاج ولا تحول الحد إلى اختبار عكسي

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

حتى الأعداد الصغيرة لا تشهد بالغياب وحدها. على الرؤوس الستة ارسم AB وAC وBC فقط، واترك D وE وF معزولة؛ توجد3 حواف ومثلث ABC. إذن كون العدد أقل بكثير من9 لا يكفي لنفي المثلث.

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

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

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