ثابت کنید حداقل ‎$n! \times (n-1)! \times \dots \times 2! \times 1!$‎ مربع لاتینِ ‎$n$‎ در ‎$n$‎ متفاوت وجود دارد.

راهنمایی ‎۱‎: با استقرای قوی ثابت کنید گرافی دو بخشی که ‎$\delta \geq k$‎ و شرط هال را داشته باشد، حداقل ‎$k!$‎ تطابق کامل دارد.

راهنمایی ‎۲‎: به اثبات زیر برای وجود یک تطابق در گراف دوبخشی با شرط هال توجه کنید:

فرض کنید گراف دو بخشی ‎$G$‎ با بخش‌های ‎$X$‎ و ‎$Y$‎ داریم که به ازای هر ‎$S\subseteq X$‎ داریم ‎$|S| \leq |N(S)|$‎. می‌خواهیم با استقرا بر روی ‎$|X|$‎ ثابت کنیم گراف مورد نظر تطابقی دارد که ‎$X$‎ را می‌پوشاند.

کوچک‌ترین مجموعه‌ی ناتهی ‎$S\subseteq X$‎ را در نظر بگیرید که ‎$|S| = |N(S)|$ (اگر چنین مجموعه‌ای وجود نداشته باشد، به سادگی به یکی از راس‌های بالا یکی از راس‌های پایین را منتسب می‌کنیم و باز شرط هال برقرار است). یکی از راس‌های ‎$S$‎ مانند ‎$v$‎ را به یکی از راس‌های مجاورش در ‎$N(S)$‎ مانند ‎$u$‎ منتسب می‌کنیم و ثابت می‌کنیم ‎$G'=G-v-u$‎ شرط هال را دارا می‌باشد.

فرض خلف می‌کنیم. فرض کنید ‎$T'\subseteq X'=X-v$‎ شرط هال را نقض کند یعنی ‎$|T'|>|N'(T')|$ (که ‎$N'$‎ یعنی همسایه‌ها بعد از حذف ‎$u$‎ و ‎$v$‎) چون قبل از حذف ‎$u$‎ شرط هال بر قرار بوده یعنی ‎$|T'|=|N(T')|$ (بزرگ‌تر نبوده چون با حذف ‎۱‎ راس کوچکتر شده)، پس ‎$u\in N(T')$.‎ ‎ $$|S|‎ + ‎|T'| = |N(S)|‎ + ‎|N(T')|$$ ‎ از طرفی بنابر شرط هال ‎ $$|S\cup T'| \leq |N(S\cup T')| = |N(S) \cup N(T')|$$ ‎ از تفریق دو رابطه اخیر به این نتیجه می‌رسیم که ‎ $$|S\cap T'| \geq |N(S)\cap N(T')| \geq |N(S\cap T')|$$ ‎ ولی چون شرط هال برقرار است باید نامساوی اخیر تساوی باشد.

پس مجموعه‌ی ‎$S\cap T'$‎ را یافتیم که از ‎$S$‎ کوچک‌تر است و شرط هال به صورت تساوی برای آن صدق می‌کند که با کمینه بودن اندازه‌ی ‎$S$‎ تناقض دارد (‎$S\cap T'$‎ نمی‌تواند تهی باشد زیرا می‌دانیم ‎$u$‎ در ‎$N(S)$‎ و ‎$N(T')$‎ هست و بنابر استدلالهای مطرح شده ‎$|S\cap T'| = |N(S) \cap N(T')|$‎. هم‌چنین ‎$v$‎ در ‎$S$‎ هست و در ‎$T'$‎ نیست پس ‎$S\cap T' \neq S$‎).

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