پاسخ : گراف با دلتای کوچیک بیشتر از kd
من راهوبه صورت کلی می گم
اگه جایی کسی توضیح اضافه خواست بگه که بگم
استقرا رو k می زنیم حکم
واسه اثبات حکم استقرا یه گراف با v=nk,&=kd
درنظر می گیریم
n تا راس این گراف به عنوان یه زیرگراف القایی برمی داریم و بهش می گیمA و به بقیه رووس هم می گیمB
حالا A1 مجموعه رووسی از A هستند که درجشون تو A از d کمتره
A2=A-A1
به همین صورت B1 را مجموعه رووسی از B می گیریم که درجشون از kd کمتره
B2=B-B1
حالا مادامی که تعداد اعضای A1,B1 بزرگتر از صفر بود میایم جای یه راس از A1 با B1 عوض می کنیم و جابه جایی های بعدی رو بعد از این جابه جایی انجام می دیم که با تعریف مجموعه هایی که در بالا تعریف شد تناقض نداشته باشه
این کار پایان پذیره چون تو هر مرحله حداقل یدونه به یالای A اضافه می شه و یالای این گراف سقف داره
پس وقتی متوقف می شه حداقل یکی از A1,B1 تعداد اعضاشون صفره چون اگه این طور نباشه می شه تعداد یالا ی A رو افزایش داد
اگه A1 صفر باشه A به عنوان جوابه
اگه B1 صفر باشه B میفته تو فرض استقرا
------------
یاحق
