====== سوال ۸ ======

ثابت کنید حداقل ‎$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$‎).

  * [[سوال ۹|سوال بعد]]
  * [[سوال ۷|سوال قبل]]