اینکه دور به طول زوج نداریم خیلی خوبه و خوبیش هم اینه که هیچ دوری به جز یال های اصلی دور یال دیگری ندارد ( منظور از یالهای اصلی ، یالهایی است که با حذف آنها دوریت دور از بین برود )
بدین منظور یک دور را در نظر میگیریم ( اگر دوری وجود نداشت پس با یک جنگل مواجه ایم و میدونیم جنگل یه گراف دو بخشیه چون هر مولفش درخته و سادست که درخت دو بخشیه پس میشه حتی با دو رنگ رنگ آمیزیش کرد چه برسه به سه تا) حالا که یه دورو در نظر گرفتیم ، به طور مطلوبی رنگ آمیزیش میکنیم ( کاری با رئوس خارج از دور نداریم ). ( چطوری ؟؟)

خب میدونیم این دور یه سری راس همسایه داره که جزو دور نیستن ، این راسا میدونیم به هم مسیر ندارن . چون اگر مسیر داشتن اونوقت یه دور به طول زوج توش پیدا میشد و این با گفته سوال همخوانی نداره. ( مسلمه که میشه با نقاشی paint شکلشو به طور واضح کشید تا همه بفهمن ولی به نظرم لزومی نداره و درکش خیلی سادست )

پس با حذف دور ، هر کدوم از همسایه هاش میفتن توی یه مولفه و هیچ دو تایی با هم نیستن (این موضوع فایده ی بزرگی داره اونم اینکه الان مساله رو برای زیر مساله های کوچکتر یعنی همون مولفه های به وجود اومده حل میکنیم و چون هر مولفه فقط یه یال به دور داره برای همین فقط راس متصل به دور توی هر مولفه رنگش به طور یکتا تعیین میشه و میدونیم این فرقی نداره با اینکه رنگش یکتا نباشه چون بالاخره رنگش باید یه چیزی باشه دیگه ( الان کسی سر در اورد ؟ ) !) با اینحساب میشه همین عملیات رو برای هر دور انجام داد تا اینکه دیگه هیچ دوری نمونه و اونوقت با یه جنگل طرفیم که میشه خیلی ساده رنگش کرد.