Skip to main content
3 of 3
deleted 2 characters in body
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 (all vertices have 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$ is even. Since the cycle space of $G$ is generated by the facial cycles of $G$ (take the symmetric difference of all faces inside the cycle), this implies that every cycle of $G$ is even. Hence $G$ is bipartite.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187