نمیدونم درسته یا نه ولی فک کنم درسته:دی تعداد دورهایی ک ممکنه تشکیل بشه با طول 2و3و4و...,n حداکثر n-1 است. اگه گراف همبند باشه:یک درخت فراگیر رو میگیریم ک مسلما n-1 یال داره. حالا 3/4n+1 یال را یکی یکی وارد میکنیم:با اضافه کردن هر یال یک دور حداقل اضافه میشه اگه یالی ازین دور قبلا عضو دور دیگری بود حداقل دو دور اضافه میشود(اجتماع دو دور منهای اشتراک دو دور)پس هر یال یا یک دور اضافه میکنه یا حداقل دو دور. حالا میخایم تعداد یال هایی ک یک دور اضافه میکنن ماکسیمم شه. دوری ک یک دور اضافه میکنه رو اس مینامیم(الکی:دی). میدانیم یال هایی ک هر دور اس(زمان اضافه شدنش)اشغال میکنه نباید توسط دور دیگری اشغال شده باشد و طول هر کدام با هم فرق دارد اگر حداکثر بتوان x تا اضافه کرد شرط روبرو باید برقرار بشه: 1+2+...+n-1>=x (پدرم در اومد) به ازای n بزرگتر از 3 فک کنم x از n/2 باید کوچیکتر باشه پس تعداد یال های اس حداکثر n/2 میشود حالا ازون 3/4n+1 این n/2 رو کم کنیم یال هایی میمونه ک حداقل دو دور اضافه میکنن1/4n+1دو برابرشو جمع کنیم با n/2 حداقل n+2 دور تشکیل میشود پس حداقل دو دور با طول یکسان داریم حالا اگه گراف ناهمبند باشه:استقرا قوی میزنیم حداقل یه مولفه هست ک بیشتر مساوی 7/4 تعدادش یال داشته باشه

شک دارم درسته یا نه ولی میزارمش شما بهم بگید درسته یا نه

اگر دارای دور نباشه حداکثر 1 - n یال داره و اگه تنها دارای یک دور باشه n یال دارهمن بزرگترین دور رو در نظر گرفتم

حالا این گراف مورد نظر یال اضافی هم داره