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.

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email