پاسخ : سوال گراف
سوال جالبی بود، فقط اضافه می کنم تطابق کامل یعنی یه مجموعه یال M که هر راسی در سر دقیقا یکی از این یال ها اومده باشه. ( => هیچ دو یالی راس مشترک ندارند )
اوّل ثابت می کنیم اگه g تطابق کامل داشته باشه می شه به مسیر های به طول سه افراز کرد: همه یال ها تطابق رو حذف می کنیم. ==>...