سوالات المپیاد:دوره ی تابستان:دوره ی ۱۲:گراف:سوال ۱
سوال ۱
گراف دوبخشی داریم که هر بخش آن n راس دارد و درجهی هر راس آن حداقل n2 است.
نشان دهید اگر M تطابقی با کمتر از n یال باشد، نسبت به M یک مسیر افزایشی به طول حداکثر ۳ داریم.
ثابت کنید برای 1≤k≤n، تعداد تطابقهای k−1 یالی حداکثر n2 برابر تعداد تطابقهای k یالی است.