Erdős–Gyárfás conjecture
گراف تھیوری میں، 1995 میں مشہور ریاضی دان پال ایرڈس اور ان کے ساتھی آندرس گائرفس کے ذریعہ غیر مصدقہ ایرڈس-گائرفس قیاس آرائی میں کہا گیا ہے کہ کم از کم ڈگری 3 والا ہر گراف ایک سادہ سائیکل پر مشتمل ہوتا ہے جس کی لمبائی دو کی طاقت ہوتی ہے۔ ایردوس نے قیاس کو ثابت کرنے کے لیے $100، یا جوابی مثال کے لیے $50 کا انعام پیش کیا۔ یہ ایردوس کے بہت سے قیاس آرائیوں میں سے ایک ہے۔ اگر قیاس غلط ہے، تو ایک جوابی مثال ایک گراف کی شکل اختیار کرے گی جس میں کم از کم ڈگری تین ہو جس میں دو چکروں کی طاقت نہ ہو۔ گورڈن روئل اور کلاس مارکسٹروم کی کمپیوٹر سرچز کے ذریعے یہ معلوم ہوتا ہے کہ کسی بھی جوابی مثال میں کم از کم 17 عمودی ہونے چاہئیں، اور کسی بھی کیوبک جوابی مثال میں کم از کم 30 عمودی ہونے چاہئیں۔ مارکسٹروم کی تلاشوں سے 24 عمودی حصوں پر چار گراف ملے جن میں صرف پاور آف ٹو سائیکلوں میں 16 عمودی حصے ہوتے ہیں۔ ان چار گرافوں میں سے ایک پلانر ہے۔ تاہم، ایرڈس-گیارفس قیاس اب 3 منسلک کیوبک پلانر گرافوں کے خصوصی معاملے کے لیے درست جانا جاتا ہے۔ سائیکل کی لمبائی کے ناگزیر سیٹوں سے گراف کی ڈگری سے متعلق کمزور نتائج معلوم ہیں: لمبائی کا ایک سیٹ S ہے، جس میں |S | = O (n0.99) ہے، جیسے کہ اوسط ڈگری دس یا اس سے زیادہ والا ہر گراف S میں اپنی لمبائی کے ساتھ ایک سائیکل پر مشتمل ہوتا ہے، اور ہر گراف جس کی اوسط ڈگری n کے تکرار شدہ لوگرتھم میں ایکسپونینشل ہوتی ہے اس میں لازمی طور پر ایک سائیکل ہوتا ہے جس کی لمبائی دو کی طاقت ہوتی ہے۔ یہ قیاس طیارہ پنجے سے پاک گرافوں اور ان گرافوں کے لیے بھی درست جانا جاتا ہے جو بڑے محرک ستاروں سے بچتے ہیں اور ان کی ڈگریوں پر اضافی رکاوٹوں کو پورا کرتے ہیں۔ حوالہ جات۔ ۔ ۔ ۔ ۔ بیرونی روابط ایکزو، جیفری، گرافز ودآؤٹ سائیکلز آف اسپیسیفائیڈ لینتھ ویسٹ، ڈگلس بی۔، ایرڈس گیارفس کانجیکچر آن 2-پاور سائیکل لینتھز، اوپن پروبلمز-گراف تھیوری اور کمبینٹوریکس کانجیکچرس گراف تھیوری میں حل نہ ہونے والے مسائل گیارفس کانجیکچر