This question on MSE has not received a satisfying answer. It can be summarized as follows:
Question: Is is true that the edge-graph of a (convex) polytope is bipartite if and only if all 2-faces are $2n$-gons?
This is motivated by the fact that a graph is bipartite if and only if all its cycles are of even length. The hope is then that for polytopes it suffices to check the facial cycles instead of all cycles.
I would like to ask this question more generally for polytopal complexes.
Question: Is is true that a simply connected polytopal complex has a bipartite edge-graph if and only if all its 2-faces are $2n$-gons?
Simply connected is necessary, because there are counterexamples otherwise (see the image below; this one was already mentioned in the original post on MSE).
Even more general, I have the feeling this might be true for all polytopal complexes with a trivial first homology group. The idea is as follows:
- Fix a vertex $v$ of the complex.
- For a vertex $w$, consider two paths $P_1$ and $P_2$ from $v$ to $w$.
- Somehow use the fact that the union of these paths is a boundary (by trivial first homology group) to show that the paths have the same parity (that is, the same length mod 2).
- Define a bipartition of the edge graph by assigning to each vertex $w$ the partiy of the paths from $v$ to $w$.
Apparently there are some gaps in the third step that I do not know how to fill in.