We will use induction. Just notice that there exist 3 consecutive vertices with different colours.

Supercali wrote: We will use induction. Just notice that there exist 3 consecutive vertices with different colours. The idea is correct but some more detail is required. Let the three colours be red (R), blue (B), and green (G). Let the convex polygon be $A_1A_2 \cdots A_n$. The colour of a vertex $v$ is denoted by $c(v)$. Suppose some colour, say red, occurs only once as the colour of some vertex, say $c(A_n) = R$. Then the vertices from $A_1$ to $A_{n-1}$ must be coloured alternately with the colours $B$ and $G$. Thus the triangulation $A_nA_1A_2, A_nA_2A_3 , \cdots , A_nA_{n-2}A_{n-1}$ works. Otherwise for each colour, there exist at least two vertices with that colour. Here, we show that Supercali's claim is true. Indeed, assume that it was not true. Let $c(A_1) = R$ and $c(A_2) = B$, say. Then by our assumption, $c(A_3) = R$, $c(A_4) = B,$ etc, and the whole colouring is determined by only red and blue. But this would lead to a contradiction, as the colour green occurred nowhere. Thus some vertex $v$ has neighbours of different colours. The triangle $T$ that they form has all three colours different. Separate this triangle, and the remaining polygon is $n-1$-sided, and each colour occurs at least once in it ( this is why we need to make cases; we need each colour to occur at least once). Now this is induction.

I came here so happy, thinking that I had solved the problem and that I would post a solution. Saw bio's solution and told myself that people can think alike.

Induct on the number of sides, its obvious for $n=3$, so assume it holds for $n$ and we need to prove it for $n+1$ First, see that there must exist three consecutive vertices of different colours. Suppose not, then pick any two adjacent vertices with different colours. Call the colours $A,B$, so we get that the next vertices need to be coloured $A,B,A,B$ and so on, and so all vertices have to be coloured only $A,B$, which is impossible. So, pick any triple of three consecutive vertices of different colours, call them $v_1,v_2,v_3$ and let them be coloured with colours $A,B,C$. Then, we can draw diagonal $v_1v_3$ and then use the induction hypothesis on all the vertices except $v_2$. This works (almost always) because $v_1, v_3$ are indeed different colours, as required by the problem. The only problem arises when $v_2$ was the only vertex of colour $B$, because then the remaining polygon does not have any vertex of colour $B$ and so the induction hypothesis doesnt work. But this case is only possible if the remaining polygon is a $2k$ gon with colours alternating every vertex. Call the remaining vertices $v_1, v_2, ..., v_{2k}$. Then, just draw the diagonals $v_1v_3, v_1v_5, v_1v_7....v_1v_{2k-1}$ and $v_3v_5, v_5v_7,...,v_{2k-3}v_{2k-1}$, which can easily be checked to work. Therefore, it is always possible to divide the given polygon into triangles such that all triangles have vertices of all three colours. Edit: Just realised my solution is the same as that of biomathemetics