درود

مسئله رو برای گراف ساده و همبند حل می کنیم:

کوچک ترین دور گراف را در نظر می گیریم و راسهای گراف را به دو دسته تقسیم می کنیم(آنهایی که در دور حضور دارند(k تا) و آنهایی که حضور ندارد(n-k تا)

حال یالهای گراف را به سه دسته تقسیم می کنیم(انهایی که در دو راس از دسته ی اول را به هم متصل می کنند(k تا) و انهایی که دو راس از دسته دوم را به هم متصل می کنند(n-k-1 تا) و انهایی که راسهای دسته ی اول را به دسته ی دوم متصل می کنند(۵ تا) [از اثبات این عدد ها صرف نظر کردم!!]

*تعداد یالهای دسته اول دقیقا k تاست اما یالهای دسته دوم میتونه بیشتر از n-k-1 تا باشه که در اون صورت وجود دو تا دور واضحه(چرا؟؟)

راسهای دسته ی دوم و یالهای بینشان را در نظر می گیریم(تشکیل یک درخت می دهند).۵ تا ازین راسها به راسهایی از دسته ی دوم یال دارند.۲ تایی را در نظر می گیریم که بعد از حذف مسیر بینشان 3 راس دیگر به هم متصل باشند(می دانیم وجود دارد[صرف نظر از اثبات!!])(بهشون میگیم x,y ,و به یالهایشان میگیم X,Y)

نکته:ممکنه ۵ تا راس نداشته باشیم و تعداد کمتری راس داشته باشیم یعنی یک یا چند راس بیش از یک یال به دسته دوم داشته باشند که توی اثبات مشکلی ایجاد نمی کنه(چرا؟؟)

حال راسهای متناظرشان در دسته ی اول را در نظر می گیریم.(الان کلا میخوایم روی راسهای دسته ی اول و یالهای بینشان فکر کنیم!!) می دانیم دقیقا دو مسیر بین این دو راس وجود داره(چرا؟؟) (باز هم اگه هر دو تا راس یه راس بودند ( !! )مشکلی ایجاد نمیشه)حالا می دانیم طبق اصل لانه کبوتری حداقل ۲ تا از ۳ راس دیگه(بهشون می گیم rو t)(باز هم اون موضوع مشکلی ایحاد نمیکنه!!) در یکی از این مسیرها قرار دارند.

الان واضحه که یالهای مسیر دیگر + X + Y + مسیر بین x,وy در یالهای دسته ی دوم یک دور ایجاد می کند.

الان میدانیم در یالهای دسته اول یک مسیر بین r و t وجود دارد.(دو یالی که r, t را به راس های دسته دوم وصل می کنند را Rو T می نامیم)الان راسهای متناظر r,t را در دسته دوم در نظر میگیریم.طبق یکی از فرض ها در بین یالهای دسته دوم مسیری بین این دو راس وجود دارد(کدوم فرض؟؟!!)

الان دوباره واضحه که این مسیر +R + T + مسیر بین r,t در یالهای دسته اول یک دور ایجاد می کند.

و واضحه که دو تا دور گفته شده هیچ اشتراک یالی ندارند!!

پایان اثبات

حالا

اگه گراف همبند نباشه:(همه ی مولفه های همبندی به جز یدونشون جنگل تشکیل میدن , اونا رو حذف میکنیم و مسئله رو حل می کنیم

اگر هم غیر ساده باشه که خوب اون عامل غیر ساده بودن(طوقه یا یال چندگانه) یک دور ایجاد می کند و بقیه گراف درخت نیست و یک دور دیگه داره و مسئله حله)

(سعی کردم خلاصه کنم, به خاطر کم و کاستی ها و طولانی بودن ببخشید)

سوال معروفیه اثباتش رو میتونی توی کتاب مساله های الگوریتمی دکتر قدسی ببینی مساله ۲۴ کتابش هست از معدود سوالاییش هم هست که کامل تیوریشو ثابت کرده