در گراف دو بخشی $G=(V,E)$ دو بخش گراف $U$ و $W$ هستند. د رنگ‌آمیزی یالی معتبر $c$ که به هر یال $e$ در گراف $c(e)$ را نسبت می‌دهد به طوری که دو یال مجاور هم‌رنگ نباشند، می‌گوییم یال $e$ یال $e'$ را رویت می‌کند، اگر $e$ و $e'$ در راس $v$ مشترک باشند و یکی از دو شرط زیر برقرار باشد:

• $v \in U$ و داشته باشیم، $c(e)<c(e')$.
• $v \in W$ و داشته باشیم، $c(e) > c(e')$.

اگر $S$ زیرمجموعه‌ای از یال‌ها باشد، ثابت کنید جورسازی (تطابق) $M\subset S$ وجود دارد به طوری که به ازای هر یالی مثل $e$ از $S$ یالی از $M$ وجود داشته باشد که $e$ آن را رویت کند.

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