So this question is seriously flooring me.
Let $G$ be drawn in the plane so that it satisfies:
- The boundary of the infinite region is a cycle $C$
- Every other region has boundary cycle of length $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?