گراف ساده، مسطح و ۳ـ منتظم $G$‌ داده شده است. این گراف یک دور بیرونی دارد که رئوس آن را رئوس بیرونی می‌نامیم. بقیه رئوس در داخل این دور قرار دارند. همچنین هر راس که در دور بیرونی قرار دارد، به جز دو راس مجاورش در درور بیرونی، به یکی از رئوس داخلی یال دارد. در ضمن اگر یال‌های دور بیرونی را حذف کنیم، گراف حاصل یک درخت خواهد بود.

ثابت کنید در $G$ دقیقا ۳ دور همیلتونی وجود دارد.

• سوال بعد