Explanation of the 3-connected counterexample

Consider the circuit $ a,b,d,f,h,a $ to be color 1. And assume there is a 5-cycle cover containing this circuit as one of the cycles. We distinguish the cycles by color.
Then $ (a,b) $ and $ (a,c) $ are colored with the same color (color 2) in the second cycle covering them, and similarly $ (a,b) $ and $ (a,h) $ have the same color (color 3) in the second cycle covering them. (As otherwise $ (a,c) $ is colored twice by the cycle $ (a,c,a) $ which, if allowed, quickly shows necessity of 6 colors)

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options