شمارش در گراف

Question

همه ی گرافهای$n$ راسی را بیابید که بتوان رئوس آنها را با دو رنگ آبی و قرمز بگونه ای رنگ آمیزی کرد که در هر راس ،تعداد یالهایی که از آن راس خارج شده و به راسی همرنگ با آن وصل شده است زوج باشد

Answer 1

برای حل مساله کافیست ما دو زیر گراف روی رئوس مجزا از گراف را بتوانیم پیدا کنیم که در هر زیر گراف درجه تمام رئوس زوج باشد.

اگر گراف همبند باشد این برابر است با اینکه گراف اویلری باشد.

پس باید تمام مولفه های همبندی گراف، اویلری باشند یا اینکه بتوان آن را به صورت دو زیر گراف روی رئوس مجزا نوشت که اجتماع رئوس برابر تمام رئوس مولفه باشد و هر زیر گراف اویلری باشد.