====== دور هامیلتونی ۲ ======

اولا واضح است که اگر حکم مسئله را برای درخت‌ها ثابت کنیم. برای کل گرف‌ها ثابت می‌شود، چرا که هر گراف همبند $G$ حداقل یک زیردرخت فراگیر $T$ دارد و همه‌ی یال‌هایی که در $T^3$ وجود دارند در $G^3$ هم موجود هستند. برای اثبات حکم روی درخت‌ها از استقرا استفاده می‌کنیم: «به ازای هر درخت $T$ با $n$ راس، $T^3$ شامل حداق یک دور هامیلتونی $C$ است». حال سعی می‌کنیم روی $n$‌ استقرا بزنیم ولی با کمی دقت متوجه می‌شویم که این کار عملی نیست. برای رفع این مشکل حکم استقرا را تقویت می‌کنیم: «به ازای هر درخت $T$ با $n$ راس، و هر یال $(e\in T)e$، گراف $T^3$ شامل حداقل یک دور هامیلتونی $C$‌ است به طوری که $e\in C$». حال می‌توان حکم را اثبات کرد: فرض می‌کنیم حکم برای هر درخت با $k$‌راس که $2<k\leq n$ اثبات شده باشد. می‌خواهیم حکم را برای $n$‌اثبات کنیم:

اگر یال $e$‌ را از $T$ حذف کنیم دو درخت جدید $T_1$ و $T_2$‌تشکیل خواهند شد. اگر فرض کنیم هر دو درخت $T_1$ و $T_2$  بیش از دو راس دارند (در غیر این صورت هم حکم به همین روش اثبات می‌شود) می‌توان فرض استقرای قوی شده را مانند شکل زیر روی آن‌ها اعمال کرد: $T_1$ شامل دور هامیلتونی $C_1$ است که $e_1$ را دربر داشته باشد و $T_2$ هم شامل دور هامیلتونی $C_2$ است که $e_2$ جزء آن باشد. می‌دانیم که در $T_3$ دو راس $x$‌ و $y$ به هم یال دارند. بنابراین اگر $e_1$ را از $C_1$‌و $e_2$ را از $C_2$ حذف کنیم و به مجموعه‌ی باقی‌مانده یال‌های $e$ و $xy$ را اضافه کنیم، مجموعه به دست آمده یک دور هامیلتونی در $T^3$ خواهد بود که شامل $e$ هم هست.

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