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.
If every face boundary is a cycle of even length, every face has an even degree. There are no cycles of odd degree and the graph must be bipartite. Is this enough of a proof?
Best Answer
Is this enough of a proof? I would have to say no.
If every face boundary is a cycle of even length, every face has an even degree. This is essentially saying "If X, then X." The catch is that there might be cycles that are not face boundaries.
There are no cycles of odd degree and the graph must be bipartite. This is what we need to prove (and we need to do more than assert that it is true).
May I suggest this approach:
Assume the graph has an odd cycle $C$. Assume $C$ is a minimum length cycle.
If $C$ is not a face boundary, then [???], so we can find an odd-length cycle smaller than $C$, giving a contradiction. So $C$ is a face boundary.
However, this contradicts the initial hypothesis: every face boundary is a cycle of even length.