Question

ثابت کنید هر گراف $(p-1)$-منظم که دارای $2p$ گره است، تطابق (جورسازی) کامل دارد.

ویرایشگر: پرسش‌کننده توضیح بیشتری وارد نکرده‌است.

Answer 1

پیش از هر چیزی توجه کنید که باید فرض $p\geq 2$ را بیفزائید. چون اگر $p=1$ آنگاه یک گراف دو گره‌ایِ بدون یال دارید که هیچ جورسازی‌ای ندارد چه برسد به اینکه جورسازی کاملی داشته‌باشد.

در حالی که گراف‌تان دوبخشی باشد روش دقیقا یکسانی با پاسخی که برای پرسش دیگرتان گذاشتم حکم‌تان را نتیجه می‌دهد (اینجا کلیک کنید). درجهٔ بیشینه‌تان که با درجهٔ همهٔ گره‌هایتان در اینجا برابر است، می‌شود $\Delta=p-1$. تعداد یال‌ها در اینجا به شما داده نشده‌است ولی از روی درجه‌ها و تعداد گره‌ها می‌توان آن را یافت.

$$\begin{align} & 2|E|=\sum_{v\in V}\deg (v)=\sum_{v\in V}(p-1)=(p-1)|V|=2p(p-1)\\ & \Longrightarrow |E|=\frac{2p(p-1)}{2}=p(p-1) \end{align}$$

با جایگذاری در فرمول $|K|\geq\frac{|E|}{\Delta}$ (که $|K|$ تعداد یال‌های جورسازی بیشینه است) داریم

$$|K|\geq\frac{p(p-1)}{p-1}=p$$

پس جورسازی بیشینه‌تان دست‌کم $p$ یال دارد و چون یال‌های یک جورسازی نباید در گره‌ای مشترک باشند پس $2p$ گرهٔ متمایز با این $p$ یال جور شده‌اند که یعنی همهٔ گره‌های گراف، پس این جورسازی، یک جورسازیِ کامل است.

این اثبات برای گراف‌های دوبخشی است چون از قضیهٔ Konig که برای گراف‌های دوبخشی است استفاده کرده‌ایم. برای $p=2,3$ گراف $2p$گره‌ایِ $(p-1)$-منظم، دوبخشی نیز می‌شود.