5
$\begingroup$

So this question is seriously flooring me.

Let $G$ be drawn in the plane so that it satisfies:

  1. The boundary of the infinite region is a cycle $C$
  2. Every other region has boundary cycle of length $3$
  3. Every vertex of $G$ not in $C$ has even degree

Show that $\chi(G) \le 3$, where $\chi(G)$ is the chromatic number.

I know I have to use induction and consider two cases for the first step: Whether some two non-consecutive vertices of $C$ are adjacent and in the second case I would delete an edge of $C$ and apply the induction hypothesis.

Can anyone help?

2 Answers 2