‎$G$‎، گرافی ‎$n$‎ رأسی با یال‌های ‎$e_1‎, ‎e_2‎, ‎\dots‎, ‎e_m$‎ است. می‌خواهیم تعدادی زیرگراف دوبخشی کامل فراگیر از ‎$G$‎ پیدا کنیم که هر یال ‎$e_i$‎ حداقل در یکی از این زیرگراف‌ها آمده باشد.

الگوریتمی چندجمله‌ای ارائه دهید که بگوید آیا می‌توان این کار را انجام داد یا نه، و اگر می توان حداقل چند زیرگراف لازم است؟

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