Erdős–Gyárfás conjecture
গ্রাফ তত্ত্বে, 1995 সালে প্রভূত গণিতবিদ পল এরদোস এবং তাঁর সহযোগী আন্দ্রেস গিয়ারফাস দ্বারা তৈরি অপ্রমাণিত এরদোস-গিয়ারফাস অনুমান বলে যে ন্যূনতম ডিগ্রি 3 সহ প্রতিটি গ্রাফে একটি সহজ চক্র থাকে যার দৈর্ঘ্য দুটির শক্তি। অনুমানটি প্রমাণ করার জন্য এরদোস 100 মার্কিন ডলার বা পাল্টা উদাহরণের জন্য 50 মার্কিন ডলার পুরস্কারের প্রস্তাব দিয়েছিলেন; এটি এরদোসের অনেক অনুমানের মধ্যে একটি। যদি অনুমানটি মিথ্যা হয়, তবে একটি পাল্টা উদাহরণ ন্যূনতম ডিগ্রি তিন সহ একটি গ্রাফের রূপ নেবে যার কোনও পাওয়ার-অফ-টু চক্র নেই। গর্ডন রয়লে এবং ক্লাস মার্কস্ট্রমের কম্পিউটার অনুসন্ধানের মাধ্যমে জানা যায় যে, যে কোনও পাল্টা উদাহরণের কমপক্ষে 17টি শীর্ষ থাকতে হবে এবং যে কোনও ঘন পাল্টা উদাহরণের কমপক্ষে 30টি শীর্ষ থাকতে হবে। মার্কস্ট্রমের অনুসন্ধানে 24টি শীর্ষে চারটি গ্রাফ পাওয়া গেছে যেখানে কেবলমাত্র পাওয়ার-অফ-টু চক্রের 16টি শীর্ষ রয়েছে। এই চারটি গ্রাফের মধ্যে একটি হল প্ল্যানার; তবে, 3-সংযুক্ত ঘন প্ল্যানার গ্রাফের বিশেষ ক্ষেত্রে এরদোস-গিয়ারফাস অনুমানটি এখন সত্য বলে জানা যায়, চক্রের দৈর্ঘ্যের অনিবার্য সেটগুলির সাথে একটি গ্রাফের ডিগ্রি সম্পর্কিত দুর্বল ফলাফলগুলি জানা যায়ঃ দৈর্ঘ্যের একটি সেট S রয়েছে, যার সাথে |S। = O (n0.99) রয়েছে, যাতে গড় ডিগ্রি দশ বা তার বেশি সহ প্রতিটি গ্রাফ S-এ তার দৈর্ঘ্য সহ একটি চক্র ধারণ করে এবং প্রতিটি গ্রাফ যার গড় ডিগ্রি n-এর পুনরাবৃত্ত লগারিথমে সূচকীয় হয় অবশ্যই একটি চক্র ধারণ করে যার দৈর্ঘ্য দুই শক্তি। এই অনুমানটি সমতলীয় নখ-মুক্ত গ্রাফ এবং এমন গ্রাফের ক্ষেত্রেও সত্য বলে জানা যায় যা বড় প্ররোচিত নক্ষত্রকে এড়িয়ে চলে এবং তাদের মাত্রায় অতিরিক্ত সীমাবদ্ধতা পূরণ করে। রেফারেন্স। । । । । এক্সটার্নাল লিঙ্ক এক্সো, জিওফ্রে, গ্রাফস উইদাউট সাইকেলস অফ স্পেসিফাইড লেন্থস ওয়েস্ট, ডগলাস বি., 2-পাওয়ার চক্র দৈর্ঘ্যের উপর এরডস গিয়ারফাস অনুমান, উন্মুক্ত সমস্যা-গ্রাফ তত্ত্ব এবং কম্বিনেটরিক্স অনুমান গ্রাফ তত্ত্বের অমীমাংসিত সমস্যা গিয়ারফাস অনুমান