Proving bipartition in a connected planar graph
Let $G$ be a connected planar graph with a planar embedding where every face boundary is a cycle of even length. Prove that $G$ is bipartite.
Any hints/tips will be greatly appreciated.
Solution 1:
Hint:
- Every face has boundary of even length $\Rightarrow$ every simple cycle is of even length $\Rightarrow$ every cycle is of even length $\Rightarrow$ graph is bipartite.
I hope this helps ;-)