قضیه های وجودی دور همیلتونی
==============================

لم اساسی
----------------

گراف ساده :math:`n` راسی  :math:`G` را در نظر بگیرید که دارای دو راس نامجاور :math:`a, b` می باشد به طوریکه :math:`d_a + d_b \geq n`. حالا گراف :math:`H` را در نظر بگیرید که همان گراف :math:`G` است که در آن رئوس :math:`a, b` با یک یال به هم متصل شده اند. ادعا می کنیم گراف :math:`G` دور همیلتونی دارد اگر و تنها اگر گراف :math:`H` دور همیلتونی داشته باشد.

طرف اول اثبات واضح است زیرا اگر :math:`G` دور همیلتونی داشته باشد :math:`H` هم دارای آن دور خواهد بود. (یالی حذف نکردیم)

حالا برای اثبات طرف دوم فرض کنید :math:`H` دور همیلتونی داشته باشد. اگر این دور از یال :math:`ab` استفاده نکند :math:`G` هم همان دور را دارد و حکم اثبات می شود. پس فرض کنید این دور از یال :math:`ab` استفاده می کند در نتیجه باید مسیری همیلتونی در :math:`G` وجود داشته باشد که از :math:`a` شروع و به :math:`b` ختم می شود.

حالا فرض کنید مسیر همیلتونی ما :math:`a = v_1, v_2, ..., v_n = b` می باشد. اگر :math:`v_1` به :math:`v_i` یال داشته باشد و :math:`v_n` به :math:`v_{i-1}` یال داشته باشد آنگاه می توانیم یک دور همیلتونی در گراف :math:`G` بیابیم. (از :math:`v_1` به مستقیم به :math:`v_i` بروید سپس مسیر :math:`v_i` تا :math:`v_n` را طی کنید سپس از :math:`v_n` مستقیم به :math:`v_{i-1}` بروید سپس مسیر :math:`v_{i-1}` تا :math:`v_1` را طی کنید).

.. figure:: /_static/dot/Ore_Theorem_Proof.svg
   :width: 80%
   :align: center
   :alt: اگه اینترنت یارو آشغال باشه این میاد

حالا به ازای هر راسی مثل :math:`v_i` که :math:`v_1` به آن یال دارد :math:`v_{i-1}` را قرمز کنید و به ازای هر راسی مثل :math:`v_i` که :math:`v_n` به آن یال دارد :math:`v_i` را آبی کنید. اگر بتوانیم ثابت کنیم راسی وجود دارد که هم قرمز هم آبی شده باشد مسئله حل خواهد شد. می دانیم که طبق فرض :math:`d_a + d_b \geq n` پس تعداد راس هایی که رنگ کردیم حداقل :math:`n` است. از طرفی راس :math:`v_n` هیچگاه رنگ نمی شود (چرا؟). پس :math:`n-1` راس داریم که حداقل :math:`n` بار رنگ شده اند پس طبق اصل لانه کبوتری راسی وجود دارد که دو بار رنگ شده باشد. پس راسی وجود دارد که همزمان آبی و قرمز شده باشد در نتیجه در :math:`G` دور همیلتونی وجود دارد.

دیگر قضایا
-----------------

در اینجا به بیان چند قضیه می پردازیم که می توانید به راحتی با لم اساسی که بیان شد اثبات کنید.

- اگر در گراف :math:`G` درجه هر راس حداقل :math:`\frac{n}{2}` باشد آنگاه در این گراف دور همیلتونی وجود دارد.
- اگر در گراف :math:`G` به ازای هر دو راس نامجاور :math:`a` و :math:`b` داشته باشیم :math:`d_a + d_b \geq n` در این گراف دور همیلتونی وجود دارد.