فرض کنید G یک گراف دوبخشی باشد به طوری که هر بخش دقیقا n راس داشته باشد و دنبالهی درجههای راسهای یک بخش r1,r2,…,rn باشد. قضیه برگمن بیان میدارد که تعداد تطابقهای کامل این گراف کمتر یا مساوی است با
n∏i=1(ri!)1ri
(a) شما باید با استفاده از قضیهی برگمن تعمیم زیر را اثبات کنید:
فرض کنید G یک گراف دوبخشی باشد به طوری که بخش X دقیقا m راس و بخش Y دقیقا n≥m راس داشته باشد. اگر دنبالهی درجههای راسهای بخش Xبه صورت r1,r2,…,rm باشد، آنگاه تعداد تطابقهای با اندازهی nکمتر یا مساوی است با:
n!n−mn(n−m)!n∏i=1(ri!)1ri
(b) فرض کنید S یک زیرمجموعه از خانههای یک مربع n×n باشد به طوری که دقیقا ri خانه در سطر iام و cj خانه در ستون j ام داشته باشد. با استفاده از قضیهای که در قسمت قبل اثبات کردید ثابت کنید: تعداد مربعهای لاتین جزیی که میتوان در S قرار داد کمتر یا مساوی است با:
(n∏i=1(n!)n−rin1(n−ri)!)(n∏i=1ci−1∏j=0(n−j)!1(n−j)!)