Claim 1: In each triangulation with ~N \ge 4~, there are at least two "ears", i.e., triangles that share two sides with the input polygon.

Sketch of the proof: Induction. The claim holds for a square. Let a diagonal divide the polygon into two smaller polygons. If one of them is is a triangle, that is an ear. Otherwise, we make an inductive argument.

First, we will describe the process of triangulation checking. A naive algorithm will remove ear by ear. This can be more or less efficiently implemented and you could have solved the first two subtasks using an ~\mathcal O(N^2)~ implementation.

Here we present one possible ~\mathcal O(N \log N)~ approach.

For each diagonal ~ab~, we construct directed edges ~(a, b)~ and ~(b, a)~. Now, let's sort all ~2(N-2)~ edges by the distance of their endpoints in the starting polygon. Here, we consider the distance between two nodes as the number of polygon sides between them in clockwise direction. It is clear that the first element of this sorted array must be an ear. It can be proved that if we trim the ears in this order, in each moment the first remaining edge will be a part of the ear that needs to be removed in that step. If it is not, then the triangulation is not valid.

A linked list can be used to keep the current order of outer polygon nodes. Both color and triangulation checks can be done at the same time.