Graph Theory গ্রাফ থিওরির সেটআপ

একটি ৬ জনের গ্রুপে সবাই একে অপরের বন্ধু বা অচেনা। প্রমাণ করো যে সেখানে অবশ্যই তিনজন বন্ধু বা তিনজন অচেনা থাকবে

Graph Theory দিয়েই (আর বেশি পরিচিতভাবে Ramsey Theory) খুব সুন্দরভাবে প্রমাণ করা হয়। এটা আসলে ক্লাসিক ফলাফল: R(3,3)=6।

গ্রাফ থিওরির সেটআপ

৬ জনকে ৬টা vertex ধরো।

যে দুইজন বন্ধু → তাদের মাঝে লাল (red) edge

যে দুইজন অচেনা → তাদের মাঝে নীল (blue) edge

কারণ “সবাই একে অপরের বন্ধু বা অচেনা”—মানে প্রতি জোড়ার মধ্যে ঠিক এক রঙের edge আছে।

আমাদের দেখাতে হবে: অবশ্যই

• তিনজনের একটি দল হবে যাদের তিনটি edge-ই লাল (৩ জন বন্ধু)

অথবা

• তিনজনের একটি দল হবে যাদের তিনটি edge-ই নীল (৩ জন অচেনা)

অর্থাৎ একটি monochromatic triangle থাকবেই।

প্রমাণ (খুব সহজ কৌশল)

একজনকে ধরো, নাম ধরি A।

A বাকি ৫ জনের সাথে যুক্ত—সেগুলো ৫টা edge। প্রতিটা edge হয় লাল নয়তো নীল।

Pigeonhole Principle অনুযায়ী ৫টা edge দুই রঙে ভাগ হলে—

কমপক্ষে ৩টা edge একই রঙ হবে।

অর্থাৎ, A-এর সাথে বাকি ৫ জনের মধ্যে অন্তত ৩ জন হয়:

• A-এর বন্ধু (লাল edge), অথবা

• A-এর অচেনা (নীল edge)

কেস ১: A-এর ৩ জন বন্ধু আছে

ধরি তারা B, C, D (A–B, A–C, A–D লাল)।

এখন দেখো B, C, D নিজেদের মধ্যে কী সম্পর্ক:

• যদি B–C, C–D, D–B এর মধ্যে কোনোটা লাল হয়, ধরো B–C লাল

তাহলে A, B, C তিনজনই পরস্পরের বন্ধু ⇒ লাল ত্রিভুজ ✅

• আর যদি B–C, C–D, D–B—এই তিনটিই নীল হয়

তাহলে B, C, D তিনজনই পরস্পরের অচেনা ⇒ নীল ত্রিভুজ ✅

দুইভাবেই কাজ হয়ে গেল।

কেস ২: A-এর ৩ জন অচেনা আছে

এটা পুরোপুরি একই যুক্তি, শুধু রঙ উল্টো:

ধরি তারা B, C, D (A–B, A–C, A–D নীল)।

• যদি B–C এর মতো কোনো edge নীল হয় ⇒ A, B, C তিনজন অচেনা ✅

• না হলে B–C, C–D, D–B তিনটিই লাল ⇒ B, C, D তিনজন বন্ধু ✅

সুতরাং সব ক্ষেত্রেই ৩ জন বন্ধু অথবা ৩ জন অচেনা পাওয়া যাবেই। প্রমাণ শেষ।