Very nice problem. Let me slightly generalize it: Generalized problem. Let $n$ be an even positive integer. A diagonal of an $n$-gon is called good if it divides the $n$-gon into two polygons each with an odd number of sides. An $n$-gon was split into triangles with non-intersecting diagonals, exactly $n/2-1$ of which are good. The triangles are colored into two colors such that no two triangles that border each other are colored with the same color. Prove that there is the same number of triangles colored with one color as with the other. Solution. So we have a triangulation of an $n$-gon. Denote this triangulation by $T$. Denote the $n$-gon itself by $P$. Let us first show that (1) every triangle of $T$ has exactly one or exactly three good sides. (Here, "good side" means "side which is a good diagonal of the $n$-gon $P$".) Proof of (1). Let $ABC$ be a triangle of $T$. The vertices $A$, $B$, $C$ subdivide the boundary of $P$ in three parts: the part between $B$ and $C$, the part between $C$ and $A$, and the part between $A$ and $B$. Let $a$ be the number of sides of $P$ lying in the part between $B$ and $C$; let $b$ be the number of sides of $P$ lying in the part between $C$ and $A$; let $c$ be the number of sides of $P$ lying in the part between $A$ and $B$. Then, $a+b+c$ is the number of all sides of $P$, and thus equal to $n$. Since $n$ is even, this means that $a+b+c$ is even. Now, we need the following fact as a lemma: (2) The side $BC$ is good if and only if $a$ is even. Proof of (2). The following two cases are possible: the case when $BC$ is a side of $P$, and the case when $BC$ is a diagonal of $P$. If $BC$ is a side of $P$, then $BC$ is not good, and $a$ is not even (since $a=1$ if $BC$ is a side of $P$). Thus, (2) trivially holds in the case when $BC$ is a side of $P$. Now let us consider the case when $BC$ is a diagonal of $P$. In this case, $BC$ divides the $n$-gon $P$ into two polygons - one of them having $a+1$ sides, and the other having $b+c+1$ sides. Thus, by the definition of "good", we see that $BC$ is good if and only if $a+1$ and $b+c+1$ are odd. But since the relation $\left(a+1\text{ and }b+c+1\text{ are odd}\right)$ is equivalent to the relation $\left(a\text{ is even}\right)$ (because if $a+1$ and $b+c+1$ are odd, then $a$ is clearly even, and the converse follows from the fact that $a+b+c$ is even), this can be rewritten as follows: $BC$ is good if and only if $a$ is even. Thus, (2) is proven in the case when $BC$ is a diagonal of $P$. Thus, (2) is proven in both cases. In other words, (2) is proven. Similarly to (2), we have: (3) The side $CA$ is good if and only if $b$ is even. (4) The side $AB$ is good if and only if $c$ is even. But $a+b+c$ is even. Thus, either exactly one of the numbers $a$, $b$, $c$ is even, or all three of the numbers $a$, $b$, $c$ are even. Because of (2), (3) and (4), this rewrites as follows: Either exactly one of the sides $BC$, $CA$, $AB$ is good, or all three of the sides $BC$, $CA$, $AB$ are good. In other words, triangle $ABC$ has exactly one or exactly three good sides. Since this is proven for any triangle $ABC$ of the triangulation $P$, this yields (1). Now, it is known that every triangulation of an $n$-gon has exactly $n-2$ triangles (this was proven in http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=14341 post #6, for instance). Thus, $T$ has exactly $n-2$ triangles. Let us call a triangle from $T$ low if it contains exactly one good side, and let us call a triangle from $T$ high if it contains exactly three good sides. Let $l$ be the number of low triangles from $T$, and let $h$ be the number of high triangles from $T$. Since every triangle from $T$ is either low or high (this is a paraphrase of (1)), and since $T$ has exactly $n-2$ triangles, we have $l+h=n-2$. On the other hand, every diagonal of the triangulation $T$ appears in exactly two triangles from $T$. In other wods, for every diagonal $d$ of the triangulation $T$, we have $\left(\text{number of triangles from }T\text{ containing }d\text{ as a side}\right) = 2$. Thus, $\sum\limits_{d\text{ is a good diagonal of the triangulation }T}\underbrace{\left(\text{number of triangles from }T\text{ containing }d\text{ as a side}\right)}_{=2}$ $=\sum\limits_{d\text{ is a good diagonal of the triangulation }T} 2$ $=2\underbrace{\left(\text{number of good diagonals of the triangulation }T\right)}_{=n/2-1}=n-2$. Comparing this to $\sum\limits_{d\text{ is a good diagonal of the triangulation }T}\left(\text{number of triangles from }T\text{ containing }d\text{ as a side}\right)$ $=\left(\text{number of pairs }\left(d,t\right)\text{ with }d\text{ being a good diagonal of the triangulation }T\right.$ $\left. \text{ and }t\text{ being a triangle from }T\text{ containing }d\text{ as a side}\right)$ $=\sum\limits_{t\text{ is a triangle from }T}\left(\text{number of good diagonals of the triangulation }T\text{ which are contained in }t\text{ as a side}\right)$ $=\sum\limits_{t\text{ is a low triangle from }T}\underbrace{\left(\text{number of good diagonals of the triangulation }T\text{ which are contained in }t\text{ as a side}\right)}_{=1\text{ (since }t\text{ is a low triangle)}}$ $+\sum\limits_{t\text{ is a high triangle from }T}\underbrace{\left(\text{number of good diagonals of the triangulation }T\text{ which are contained in }t\text{ as a side}\right)}_{=3\text{ (since }t\text{ is a high triangle)}}$ (since every triangle from $T$ is either low or high) $=\underbrace{\sum\limits_{t\text{ is a low triangle from }T} 1}_{=\left(\text{number of low triangles from }T\right)} + \underbrace{\sum\limits_{t\text{ is a high triangle from }T} 3}_{=\left(\text{number of high triangles from }T\right)\cdot 3}$ $=\underbrace{\left(\text{number of low triangles from }T\right)}_{=l} + \underbrace{\left(\text{number of high triangles from }T\right)}_{=h}\cdot 3$ $ = l+3h$, we get $l+3h=n-2$. Comparing this with $l+h=n-2$, we see that $3h=h$, so that $h=0$. Thus, there are no high triangles from $T$, so that every triangle from $T$ must be low (since every triangle from $T$ is either low or high). Now let the two colors that we used to color the triangles be black and white. Then, every good diagonal of $T$ belongs to two triangles, one of which must be black and the other one white (because these two triangles border each other, and hence must have different colors). So, we see that every good diagonal of $T$ is a side of one and only one black triangle from $T$. Conversely, every black triangle from $T$ has one and only one good side (because it is low, since every triangle from $T$ is low). This clearly yields a one-to-one correspondence between black triangles from $T$ and good diagonals of $T$. Thus, the number of black triangles from $T$ equals to the number of good diagonals of $T$. Similarly, the same holds for white triangles. Thus, the number of black triangles from $T$ equals to the number of white triangles from $T$.

Whoops this is probably the same as the solution in #2, but I'll try to write it a bit more concisely.

This seems a bit different from above approaches. We prove the result for a $2n$-gon with $n-1$ good diagonals. Say a diagonal is bad if it is not good. We include the sides of the polygon as bad diagonals, and we specify that bad diagonals which are not sides are interior bad diagonals. Claim: There is no triangle with all three of its sides bad. Proof: Straightforward parity check. $\Box$ Claim: The $n-2$ interior bad diagonals partition the $2n$-gon into quadrilaterals. Proof: Observe that the interior bad diagonals create $n-1$ polygons; each side of the $2n$-gon is a side of exactly one of these polygons, and each interior bad diagonal is a side of exactly two of these polygons. So, the average number of sides in one of these polygons is \[\frac{2(n-2) + 2n }{n-1} = 4.\]By the previous claim, no triangle exists, so equality with the average must hold for all $n-1$ polygons and they are all quadrilaterals. $\Box$ It is clear that in the final triangulation, each quadrilateral will have two triangles of opposite colors, so we are done.