فرض کنید n یک عدد طبیعی باشد. از ورودی دو مورد زیر به ما داده میشود:
میخواهیم تعدادی از یالهای مجموعهی A را به درخت اضافه کنیم، طوری که گراف حاصل دوهمبند شود. پاسخ مسئله، کمینهی تعداد یالهایی است که اضافه میکنیم (اگر دوهمبند کردن گراف ممکن نبود، پاسخ را −1 در نظر میگیریم). الگوریتمی با زمان چندجملهای ارائه کنید که پاسخ مسئله را پیدا کند.