میدانیم پس از هر چند بار برگذاری میهمانی ، تغییری در همبندی گراف به وجود نمی آید و تعداد مولفه ها همواره ثابت است ( چرا ؟؟ ) بنابراین اگر دو راس مذکور در سوال در دو مولفه ی جدا هم از باشند ، هرگز یالی به هم نخواهند داشت چون در آن صورت از تعداد مولفه ها یک واحد کم میشود. ثابت میکنیم پس از n مهمانی ( هر راس یکبار ) هر دو راسی یا با هم مجاورند یا در دو مولفه جدا قرار دارند. به عبارتی میخواهیم بگویمم » پس از n میهمانی هر دو راسی که در ابتدا به هم مسیر داشتند هم اکنون به هم وصل اند.

وقتی راس v میهمانی میگیرد ، آنگاه دیگر هیچ دو راسی نیستند که در مسیر بینشان از v بگذرند. ( منظور کوتاه ترین مسیر است) زیرا اگر مسیر P قبلن به ترتیب از رئوس a, v, b رد میشده ، پس از برگذاری میهمانی ( که میزبانش وی است ) a به b متصل میشود و مسیر p که همان آپدیت شده ی P است ، از رئوس ab رد میشود و دیگر v در هیچ مسیری مشاهده نمیشود. (البته به جز مسیر هایی که v یکی از دو سر آنهاست )

دیدیم که وقتی v مهمانی گرفت ، دیگر در هیچ مسیری ظاهر نشد ، حال اگر همه ی n راس ، مهمانی بگیرند دیگر در هیچ مسیری هیچ راسی ظاهر نمیشود ( منظور در بین مسیر است ) که به عبارتی یعنی هر دو راسی که قبلن به هم مسیر داشتند اکنون به جای مسیر به هم " یال " دارند. پس جمله ی اولمان ثابت شد »

پس از n میهمانی هر دو راسی که در ابتدا به هم مسیر داشتند هم اکنون به هم وصل اند.
بنابراین اگر در پایان دو راس به هم متصل نباشند ، یعنی در دو مولفه جدا قرار دارند که بدین معنی است که هرگز به هم متصل نخواهند شد ( حتی اگر بی نهایت مهمانی دیگر هم برگذار کنید ) چون در آن صورت از تعداد مولفه ها کم میشود که با گفته اول ما در تناقض است.

معذرت میخوام ، فکر کنم زیادی گنگ بود ، اگه راه حل ساده تری وجود داره دریغ نکنید.

من هم یک راه حل پیشنهاد میکنم: اگر بین اون دو نفر هیچ مسیری از آشنایان وجود نداشته باشه که بدیهیه هیچ وقت آشنا نمیشن. در غیر این صورت کوتاهترین مسیر آشنایی رو در نظر بگیرید. هر بار یکی از افراد داخل اون مسیر یک مهمانی بده طول مسیر بین این دو نفر یک واحد کم میشه. پس به هر ترتیبی مهمانی ها برگزار بشه بعد از این که همه افراد داخل مسیر مهمانی گرفتند طول مسیر بین دو نفر به یک میرسه، یعنی مستقیما با هم آشنا خواهند بود.

سلام

مساله رو به گراف مدل می کنیم. افراد رئوس و آشنایی رو با یال نشون میدیم. اینکه اگه 2 رأس در 2 مولفه جدا از هم باشن هیچ وقت به هم یال نخواهند داشت که واضح است. میخواهیم ثابت کنیم که در آخر کار، هر مولفه، گراف کامل خواهد شد. مساله را برای 1 مولفه حل میکنیم و هیچ فرقی هم نداره. برای این کار، کوتاه ترین مسیر بین هر 2 رأس دلخواه رو در نظر میگیریم. اگه طولش 1 باشه که حله در غیر این صورت، به ازای هر رأس موجود در این مسیر، اگه اون رأس مهمانی بگیره، طول کوتاه ترین مسیر 1 واحد کم میشه. به عبارتی، به ازای مهمانی گرفتن تمام رئوس موجود در مسیر طبق فرض سوال، در آخر کار قطر گراف که بیشترین فاصله بین 2 رأس است، حداکثر 1 می باشد و این یعنی مولفه تبدیل به گراف کامل شده است. پس در نهایت، هر مولفه کامل شده است و از این به بعد نیز تغییری در گراف کلی ما ایجاد نمی شود.