Explanation of the 3-connected counterexample (Part II)

Now $ (b,c) $ still needs to be covered twice, which cannot be done by 1 color as then again one needs 6 colors. One of the colors has to be color 2, otherwise this will leave $ b $ towards $ a $ and $ d $ and therefore there will be no escape possibility from $ b $ for the two new colors. So the triangle $ a,b,c $ is colored with color 2. By symmetry the triangle $ f,g,h $ is also one color cycle (color 4). Now $ (c,e) $, $ (d,e) $ and $ (e,g) $ are not colored and therefore need to be in the cycle of color 3 and the cycle of color 5. But then $ e $ has degree 3 in both cycles which is a contradiction.
So a 5-cycle double cover containing this cycle does not exist.


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