با سلام.
با توجه به صورت سوال درجه هر راس یا یکه یا سه. اگه a تعداد راس های از درجه ۳ و b تعداد راس های از درجه ۱ باشن داریم:
a+b=20 (تعداد رئوس)
۳a+b=19*2 (تعداد یال ها)
از حل معادله بدست میاد که a یا همون تعداد رئوس با درجه ۳ برابر ۹ هست. مسلماً هرکدوم از این رپوس حداقل با یکی دیگه از رئوس درجه ۳ مجاوره.
برای شمارش تعداد راه های رنگ آمیزی، یه رنگ به یکی از رئوس درجه ۳ و راس های مجاور میدیم. در کل این راس و ۳ راس مجاورش رو میشه به ۴! یا همون [tex]2^{3}*3[/tex] حالت رنگ آمیزی کرد. (این ۴ راس نمیتونن یک رنگ رو دوبار بگیرن. یعنی طبق فرض مسئله رنگاشون باهم متفاوته.)
حالا نوبت به راس های از درجه ۳ای هست که به اونا تعداد حالت رنگ نسبت دادیم. (یعنی مجاور رئوس رنگ آمیزی شدست.) این راس‌ها و یکی از رئوس مجاورش رنگ آمیزی شدن و ۲ خونه مجاورش هنوز بهشون رنگ نسبت داده نشده. این دو راس رو میشه به ۲ حالت رنگ کرد. این کارو تا انتخاب حالات رنگ هر ۹ راس با درجه ۳ ادامه میدیم که مسلماً رئوس درجه ۱ مجاورشون هم رنگ میشن. بجز راس درجه ۳ اول که ۴! حالت برای رنگ آمیزی داشت، بقیه رئوس درجه ۳ هرکدام ۲ حالت دارن. پس جواب مسئلمون میشه:
[tex]2^{3}*3*2^{8}=2^{11}*3[/tex]