گراف ساده‌ی $n$ رأسی $G$ را در نظر بگیرید که دور همیلتونی دارد.

آ) نشان دهید دو زیرگراف زوج (گراف زوج، گرافی است که در آن درجه‌ی تمام رئوس، زوج باشد. گراف فرد نیز به شکل مشابه تعریف می‌شود.) مانند $H_1, H_2$ از $G$ وجود دارد، طوری که هر یال $G$ در دست کم یکی از آن دو آمده باشد.

ب) نشان دهید اگر $n$ زوج باشد، دو زیرگراف فرد $H_1, H_2$ از $G$ وجود دارد، طوری که هر یال $G$ در دست کم یکی از آن دو آمده باشد.

• سوال بعد
• سوال قبل