گراف دوبخشی داریم که هر بخش آن $n$ راس دارد و درجه‌ی هر راس آن حداقل $\frac{n}{2}$ است.

1. نشان دهید اگر $M$ تطابقی با کم‌تر از $n$ یال باشد، نسبت به $M$ یک مسیر افزایشی به طول حداکثر ۳ داریم.
2. ثابت کنید برای $1\leq k \leq n$، تعداد تطابق‌های $k-1$ یالی حداکثر $n^2$ برابر تعداد تطابق‌های $k$ یالی است.

• سوال بعد