گراف دو بخشی ‎$K_{n,m}$‎ داده شده است. ‎$n$‎ راس بخش اول را در بالا و ‎$m$‎ راس بخش دوم را در پایین قرار داده‌ایم. هر تطابق در این گراف را با رسم یال‌های تطابق با خطوط مستقیم نشان می‌دهیم. می‌خواهیم رابطه‌ی صریح تعداد تطابق‌های (نه لزوما بیشینه) را در این گراف بیابیم که رسم‌شده‌ی یال‌های تطابق با هم تقاطع نداشته باشند.

برای مثال گراف ‎$K_{2,2}$‎ دارای ‎۱‎ تطابق تهی، ‎۴‎ تطابق با یک یال، و ‎۱‎ تطابق با دو یال می‌باشد که نامتقاطع باشند.

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