Planar graphs where every face boundary is a cycle of even length are bipartite

Question

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?

Answer 1

HINT:

To write formally, pick up a vertex $v_0$ and put it in partition 1. Find points at a odd (even) distance from it and put them in partition 2 (1). Since every cycle is even you won't have a case where two vertices from the same partition are adjacent.(check why?)

Answer 2

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.

Answer 3

No, that will not be sufficient proof. It is possible to have cycles which are not face cycles, and you need to show even these cannot have odd length.

I think Rebecca's approach of assuming to the contrary $G$ is not bipartite, and choosing a minimal odd cycle works, if one chooses the odd cycle $C$ such that it's interior is minimal as a subset of the plane (rather than choosing the length to be minimal).

Let $C$ be an odd cycle such that the interior region of $C$ is minimal. Since $C$ is not a face cycle (all faces have even length by assumption), there are edges and / or vertices in the interior of $C$. Because every face of the graph is bounded by a cycle (by assumption), the graph is 2-connected. Thus there must be 2 distinct vertices $x$ and $y$ of $C$ which can be joined by a path $P: x, u_1, u_2, \dots , u_k, y$ such that every vertex $u_i$ lies strictly in the interior of $C$.

The edges of the cycle $C$ can be divided into 2 edge disjoint paths, both having $x$ and $y$ as their end vertices. Since $C$ has odd length, one of these paths has odd length, and the other has even length. Call the odd and even paths $Q_o$ and $Q_e$ respectively.

If the path $P$ has odd length, then $P \cup Q_e$ is an odd cycle, whose interior is contained entirely in the interior of $C$, a contradiction. Likewise if $P$ has even length, then the cycle $P \cup Q_o$ again gives us a contradiction.

---

You can also assume to the contrary that $G$ has an odd cycle. Consider the graph $H$ formed by any odd cycle $C$, and all the stuff in its interior. The interior faces will all be bounded by cycles of even length, and the outer face will be bounded by a cycle of odd length. Thus the sum, over all faces $f$ of $H$, of the number of edges on the boundary of the face $f$, will be odd. However every edge of $H$ lies on the boundary of two faces, and thus gets counted exactly twice in this sum. Hence the sum is even, a contradiction.

Answer 4

I'll just Brandon's argument a little more crisp and easygoing. You have already observed that in a bipartite graph, every cycle is of even length. So, it is enough to prove that the statement “every face has even length” is equivalent to this. We will first show that bipartite implies that all faces have even length, and then that if all faces have even length then all cycles have even length as well.

To see the first statement, let us take any face and a vertex $v$ on it. Now start walking from $v$ along the boundary of the face. Since the graph is bipartite, we alternately encounter vertices from the two classes, and when we reach $v$ again, we are back at its class. So we made an even number of steps, hence the length of the face is even.

For the second statement, assume that all faces have even length, and consider a cycle in the drawing, of length $l$. The region bounded by the cycle is the union of faces, let the length of those faces be $l_1,\dots , l_k$. Then the sum $\sum_{i=1}^k l_i$ counts each edge the cycle once, and each edge inside the region bounded by the cycle twice (once for both adjacent faces). Also, $\sum_{i=1}^k l_i\equiv l(\text{mod }2)$, and since all the $l_i$'s are even, so must be $l$.

This completes the proof.