یک گراف دو بخشی با مجموعه رئوس $X$ و $Y$ داده شده است. رئوس مجموعه‌ی $Y$ به دسته‌های دوتایی $(u_i,v_i)$ از رئوس افراز شده است. می‌خواهیم در این گراف، در صورت وجود تطابقی $(matching)$‌را به‌دست آوریم که همه‌ی رئوس $X$ را آلوده کند و از هر زوج $(u_i,v_i)$، یا هر دو را آلوده کند یا هیچ کدام را! برای این کار زیربرنامه‌ای داریم که در زمان چندجمله‌ای مسئله‌ی یافتن تطابق کامل رادر حالت کلی (و نه لزوما دوبخشی) حل می‌کند. نشان دهید که چگونه می‌توان با استفاده از این زیربرنامه مسئله‌ی اصلی را در زمان چندجمله‌ای حل کرد.

• سوال بعد
• سوال قبل