3-colored triangulations of the sphere $S^2$, and Sperner's Lemma

Question

I noticed something about colored triangulations of the topological sphere $S^2$ and have a question about this.

Observation. If you triangulate the sphere $S^2$ and color the vertices with three colors: then the number of 3-colored triangles is always even (or zero). In particular, there is no coloring with exactly one 3-colored triangle.

For a proof, view $S^2$ as two triangulated disks with matching coloring of the boundaries that are glued together. As their boundaries have the same number of color changes, we know from Sperner’s Lemma that their triangulations have the same number (mod 2) of 3-colored triangles. So the total number of 3-colored triangles is even or zero.

As an interesting corollary, we get the characterization: A triangulated sphere has zero 3-colored triangles iff all cycles of the triangulation have an even number of color changes.

I looked at the torus, the Klein bottle, and the projective plane, and I find that the observation is also true for them.

Edit: Just for contrast, adding an example below of a "soap bubble" surface, where the two soap bubbles share a common disk. This surface allows for triangulations with even and odd numbers of 3-colored triangles (but like the other surfaces I looked at, cannot have just one).

Question. I wonder whether this also follows from more general theorems about triangulations of surfaces, or about maximal planar graphs? I have consulted algebraic topology and graph theory texts, but could not find any results in that direction. Would you have a suggestion where else to look, or maybe a reference for that?

Answer 1

A counting proof shows that this observation is unrelated to the global topology.

Every edge is monochromatic or dichromatic. How many dichromatic edges are there? If each triangle tells you its number of dichromatic edges (either 0, 2, or 3), you can add these up and divide by two to get the total number of dichromatic edges (since every edge contributes to two triangles). So the number of trichromatic triangles must be even.

This proof works for $k$-dimensional manifolds when $k$ is even, since the number of $k$-colored $(k-1)$-simplices bounding any $k$-simplex must be 0, 2, or $k+1$.

Your corollary similarly transfers to higher even dimensions, at least for orientable manifolds, replacing "cycles of edges" with "hypersurfaces of $(k-1)$-simplices", and "even number of color changes" with "even number of $k$-colored $(k-1)$-simplices".

Answer 2

Just to close the loop on this: the double-counting argument in the answer of user Matt allows for a nice visual proof of the (2-dim.) Lemma of Sperner. Just want to capture it here, as it connects nicely with the triangulation of the sphere / the maximal planar graph in my OP question.

Start with a triangulated polygon in the plane, and label each vertex with one of 3 colors. The example just shows the boundary of such a triangulated, 3-colored polygon. Claim (Sperner’s Lemma): If the boundary has an odd number of color changes, then a 3-colored triangle exists in the polygon triangulation. In fact, more generally, an odd number of such 3-colored triangles exists.

Proof: Go to 3-dimensional space, and build a “tent” over the polygon like in the diagram: add a colored vertex, and add the edges between this additional vertex and the boundary vertices of the polygon. This way, we have effectively created a triangulation of the topological sphere $S^2$.

If the boundary of the polygon has an odd number of color changes, this gives an odd number of 3-colored triangles in the “tent” over the polygon. But from the double-counting argument in user Matt’s answer, we know an even number of 3-colored Sperner triangles must exist. Hence the polygon at the bottom must have an odd number of 3-colored triangles (at least one) in its triangulation, which completes the proof.