IMC 2006 · Day 2 · P7

Apply induction on $n$. For the initial cases $n = 3, 4, 5$, chose

the triangulations shown in the Figure to prove the statement.

Now assume that the statement is true for some $n = k$ and consider the case $n = k + 3$. Denote the vertices of $V$ by $P_1, \dots, P_{k+3}$. Apply the induction hypothesis on the polygon $P_1 P_2 \dots P_k$; in this triangulation each of vertices $P_1, \dots, P_k$ belong to an odd number of triangles, except two vertices if $n$ is not divisible by 3. Now add triangles $P_1 P_k P_{k+2}$, $P_k P_{k+1} P_{k+2}$ and $P_1 P_{k+2} P_{k+3}$. This way we introduce two new triangles at vertices $P_1$ and $P_k$ so parity is preserved. The vertices $P_{k+1}$, $P_{k+2}$ and $P_{k+3}$ share an odd number of triangles. Therefore, the number of vertices shared by even number of triangles remains the same as in polygon $P_1 P_2 \dots P_k$.