Question:

# Given a planar graph G such that all the vertices have even

Last updated: 7/4/2022

Given a planar graph G such that all the vertices have even degrees: Prove that all the regions separated out by this graph (all the faces) can be 2-colored. That is, the faces can be colored such that no two faces which share an edge can have same color. (Hint: Use induction. Look at outer rim of the graph and think about removing all the edges of the outer rim.)