Dual coloring
Task number: 4192
Show that if a planar graph has even degrees, then the chromatic number of its dual is two.
Solution
By contradiction: if the dual is not a two-colorable, it contains an odd cycle.
Such an odd cycle cannot surround a face, because the length of that cycle would correspond to the degree of the respective vertex, and this should be an even number.
Consider an odd cycle \( C \), inside which there are as few faces as possible. Because it is not a single face, two vertices on \( C \) are connected by a path \( P \) lying inside the cycle \( C \). This \( P \) divides \( C \) into two cycles. One of them is odd with a smaller number of faces inside, which is a contradiction with the minimality of \( C \).
Thus, the dual does not contain any odd cycle and is therefore two-colorable.
