Skip to main content
1 of 3
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

As Fedor Petrov mentions in the comments, a necessary and sufficient condition is that each vertex has even degree. Here is a proof.

Let $T^*$ be the dual graph of the triangulation. That is, the vertices of $T$ are the faces of the triangulation, and two faces are adjacent if they share an edge. Rephrased, your question is asking when $T^*$ is bipartite. So, it suffices to prove that a planar graph $G$ is bipartite if and only if the dual graph $G^*$ is Eulerian (has all vertices of even degree). For one direction, if $G$ is bipartite, then all cycles of $G$ are even. In particular, all facial cycles are even, and hence $G^*$ is Eulerian. For the other direction, suppose that the dual graph $G^*$ is Eulerian. Thus, each face of $G$ has an even number of vertices. Since the cycle space of $G$ is generated the facial cycles of $G$, this implies that every cycle of $G$ is even. Hence $G$ is bipartite.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187