If all 2-faces of a polytope are $2n$-gons, is the edge-graph bipartite?

Question

I wonder if I can see easily whether the edge graph of a (convex) polytope $P\subset\Bbb R^d$ is bipartite or not.

A graph is bipartite if and only if all its cycles have even length. I thought about the following: maybe, a polytope is bipartite if and only of all its 2-dimensional faces are $2n$-gons. But then, the 2-faces are not all the cycles of the edge graph. So this might not be true.

Question: If all 2-faces of a polytope are $2n$-gons, is the edge graph of $P$ bipartite?

It is certainly true for $d=3$, as the cycle space of the edge graph of $P$ (a planar graph) is generated by the facial cycles.

The argument must make use of convexity or the spherical topology of $P$, as one can easily find polytopal complexs for which this statement is false (e.g. see the image below, which is taken from here).

Answer 1

For $d=3$.

Start with a single vertex $V$, color it black.

Claim 1: Fix a vertex $v$. The parity of the distance between any vertex $v$ and $V$ is a constant.

Proof: Fix a path from $v$ to $V$. Take any other path from $v$ to $V$. Show that this can be written as the union of faces, minus the removal of edges taken twice.
Hence, the length of $v-V-v$ is even, so the paths have the same parity.

Corollary: Each vertex $v$ can be properly colored based on the parity of the distance to $V$.

Claim 2: This is a valid 2 coloring.

Proof: Take any 2 vertices $s, t$. The parity $s-V-t$ is the same as the parity of $s-t$, so they have the desired colors.

---

I'm less confident about this part.

Proof of claim 1 for higher dimensions $ d \geq 4$.

Claim 3: In a convex polytope (no holes), any edge-cycle splits the polytope into 2.
(In a sense, we want a "separating hyperplane" here, but ...)

Proof: Since we're in $\mathbb{R}^d$, orientation exists. We can walk around the cycle with a "left" and a "right" side.
For any vertex that is directly connected to the cycle on the left (resp right), color it red (resp blue).
For any vertex not on the cycle that is connected to another colored vertex, give it that color. Repeat until all of the vertices are colored (which is possible because the the vertex graph is connected).
If a vertex can inherit 2 colors, then there must be an edge that cuts within this cycle, which contradicts how convex polytopes are defined (?).

Corollary: For the cycle $v-V-v$, choose one of the halves, and then it can be written as the union of all of the faces on that half minus twice of all of the edges in that half (excluding the cycle).

Answer 2

H.S.M. Coxeter proves this in section 8.6 of his book Regular Polytopes. In section 1.6, he shows "that alternate vertices of any even-faced simply-connected map can be picked out in a consistent manner (so that every edge joins two vertices of opposite types)." He proves this by observing that any circuit of $N$ edges decomposes the map into two regions. Replacing one region by a single $N$-sided face, all faces but this one have evenly many sides, so $N$ must be even (since the number of odd faces must be even.)

Then in 8.6, he states "In fact, the argument used at the end of §1.6 may be extended to any number of dimensions, with the conclusion that alternate vertices of a simply-connected polytope or honeycomb can be selected whenever every face $\Pi_2$ has an even number of sides."

I will just quote the section:

...a circuit of edges can be shrunk to a point without leaving the manifold (i.e., without leaving the "surface" of the polytope). In other words, such a circuit is (generally in many different ways) the boundary of a two-dimensional region or "2-chain," consisting of a number of $\Pi_2$'s fitting together in such a way as to be topologically equivalent to a circle with its interior, or to the curved surface of an ordinary hemisphere. If the circuit consists of $N$ edges, we can transform the 2-chain into a complete topological polyhedron (or two-dimensional map) by adding one $N$-sided face. Hence, by the remark at the end of §1.4, if every $\Pi_2$ has an even number of sides, the number $N$ must be even too. Finally, we select those vertices of the polytope or honeycomb which can be reached from a given vertex by proceeding along an even number of edges.