نظریهٔ کونیگ نشان می‌دهد که پرسمان جورسازی بیشینه و پرسمان پوشش گره‌ای کمینه برای گرافی دوبخشی هم ارز هستند.

در گراف دو بخشی بالا، شمار جورسازی‌ بیشینه (یالهای آبی)، با پوشش گره‌ای بیشینه (گره‌‌های قرمز) یکسان و برابر با ۶ است.

جورسازی زیرمجموعه‌ای از یال‌های گراف است که هیچ جفت-یالی در این زیرمجموعه همسایه نباشند. جورسازی بیشینه بزرگ‌ترین زیرمجموعه از یال‌هاست که یک جورسازی را می‌سازند.

پوشش گره‌ی در یک گراف مجموعه‌ای از گره‌های می‌باشد که می‌بایست حداقل یک گره‌ از همهٔ یالهای گراف در این مجموعه باشد.

بازبُردها

ویرایش