Polygonal region and triangulation

Question

Let $A$ e a polygonal region and $\tau$ be a triangulation. Suppose that the triangulation can be painted with two colors. Prove that the number of triangles, incident in each interior vertex must be even.

How would I prove this?

thanks

Answer 1

Consider the graph G associated with the triangulation $\tau$ where the vertices in G correspond the faces of the triangles in the triangulation, and two vertices of G are connected by an edge if the two corresponding faces of the triangulation share a common edge.

So you can see this problem as a 2-coloring problem.

Let v be a interior vertex of $A$, in order to be an interior vertex, at least it has 3 triangles incident on v. You can clearly see that if v is interior, the associated edges for the triangles around v form a cycle with at least 3 vertices.

If the cycle has length $n=2k+1$. Let $v_1,v_2,...,v_{n-1},v_n,v_1$ be the cycle formed by v. Let $C_1$={$v_i$ such that $v_i$ is painted with color 1}, $C_2$={$v_i$ such that $v_i$ is painted with color 2}.

Without loss of generality, we can say that $v_1∈C_1$, then $v_2$ must necessarily belong to $C_2$,$v_3∈C_1$ and so on.

In general, $v_l∈C_1$ if $l$ is odd or $v_l∈C_2$ if $l$ is even.

So, we have that $v_{n-1}∈C_2$ because $n-1=(2k+1)-1=2k$.

Then $v_n$ cannot belong to $C_2$ because it is adjacent to $v_{n-1}$, and cannot belong to $C_1$ because is adjacent to $v_1$, so we need to use a different color for $v_n$ which contradicts the hypothesis.

Therefore, the cycle must have $n=2k$ length and that means that the number of triangles incident on v must be even.