Suppose that the polygon has only one vertex of some colour, say red. Then drawing all diagonals from this red vertex easily solves the problem. Therefore, in what follows we may assume that the polygon has at least two vertices of each colour. In particular we may assume that $n \ge 6$.
For a polygon with $n \ge 6$ sides, we proceed using strong induction. Assume the result holds for all convex polygons with less than $n$ sides.
Version 1. Define the distance $d(X, Y)$ between vertices $X$ and $Y$ as the minimum number of neighbouring-vertex movements which are necessary in order to get from $X$ to $Y$, and denote the corresponding path traversed by $S(X, Y)$ (this path includes the endpoints $X$ and $Y$). Let $R_1$ and $R_2$ be that pair of vertices which minimize $d(X, Y)$ over all vertex pairs of the same colour; without loss of generality, we can assume these vertices are red. Now, there must exist a non-red vertex $G$ between $R_1$ and $R_2$ (i.e. lying in $S(R_1, R_2)$); without loss of generality, this vertex is green. Now, there cannot be two blue vertices $B_1$ and $B_2$ in $S(X, Y)$, as this would imply $d(B_1, B_2) < d(R_1, R_2)$, a contradiction, since $R_1$ and $R_2$ minimize this quantity. Therefore at least one blue vertex $B$ lies outside $S(R_1, R_2)$.
Joining the green vertex $G$ to the blue vertex $B$ breaks the polygon into two smaller convex polygons each of which satisfies the conditions of the original problem. Thus by strong induction the result follows for every integer $n \ge 3$.

Version 2. By assumption there are at least two red vertices. When they are removed, we are left with two disjoint, non-empty and connected sets of vertices. Both of them contain at least one vertex that is not red. If one of these sets does not contain a blue vertex, we can pick a green one in it and a blue vertex from the other set. If both sets contain at least one blue vertex, we first pick a green vertex in one of the sets, then a blue one from the other set. Therefore, in any case, we can pick a green vertex G from one of the two sets and a blue vertex B from the other.
Joining the green vertex G to the blue vertex B breaks the polygon into two smaller convex polygons each of which satisfies the conditions of the original problem. Thus by strong induction the result follows for every integer $n \ge 3$.