فرض کنید $G$ یک گراف هم‌بند $n$ رأسی و $e$ یالی باشد. در ابتدا تمام یال‌های $G$ به رنگ داغون آبی هستند. در هر مرحله می‌توان کار زیر را انجام داد:

به ازای هر رأس، یکی از یال‌های متصل به آن را انتخاب می‌کنیم و رنگ تمام یال‌های انتخاب شده را عوض می‌کنیم (از قرمز به آبی و بالعکس). توجه کنید ممکن است یک یال دو بار انتخاب شود (از طرف هر دو رأس‌ش) که در این صورت رنگ یال دو بار عوض می‌شود(عملن تغییری نمی‌کند).

هدف این است که یک گراف رویایی بسازیم که در آن تمام یال‌ها قرمز هستند. در این سوال می‌خواهیم ثابت کنیم امکان رسیدن به هدف تنها به زوجیت $n, e$ بستگی دارد و به شکل گراف بستگی ندارد.

آ) ثابت کنید اگر $n$ زوج و $e$ فرد باشد، این کار امکان‌پذیر نیست.

ب) ثابت کنید در بقیه‌ی گراف‌ها (تمام گراف‌ها جز گراف‌های قسمت آ) می‌توان با تعدادی مرحله تمام یال‌ها را قرمز کرد.

• سوال بعد