(IMO 2006 P2)

Let $P$ be a regular 2006-gon. A diagonal of $P$ is called good if its endpoints divide the boundary of $P$ into two parts, each having an odd number of sides of $P$. The sides of $P$ are also called good. Suppose that $P$ has been subdivided into triangles by 2003 diagonals, no two of which have a point in common in the interior of $P$. Find the maximum number of isosceles triangles having two good sides that can appear in such a subdivision.
We will use a graph $G$ with a vertex for each of the 2004 triangles and an edge between two vertices if the corresponding triangles share a bad side (i.e., a side that is not good). Each vertex has a degree of 1 or 3.

The good triangles are of degree 1 (but all vertices of degree 1 represent isosceles triangles). Note also that the graph we obtain is acyclic. Let $N_{1}, \ldots, N_{k}$ be the connected components of $G$ (each of them is a tree). If $N_{i}$ has $n_{i}$ vertices, suppose that $x$ of them are of degree 1 and $y$ of degree 3. We have

\[
\begin{aligned}
x+y & =n_{i} \\
x+3 y & =2\left(n_{i}-1\right)
\end{aligned}
\]

Thus, $x=\frac{n i+2}{2}$. Consequently, the total number of vertices of degree 1 is $\frac{n_{1}+\cdots+n_{k}}{2}+k=$ $1002+k$. Note that the vertices of $N_{i}$ represent triangles that form a polygon, and the union of the polygons formed by all connected components is the original 2006-gon. Consider a new graph $H$ with a vertex for each connected component and an edge between them if the corresponding polygons share a side. Note that $H$ is connected. It therefore has at least $k-1$ edges. If $\delta_{1}$ and $\delta_{2}$ are triangles in different connected components that share a side, this side must be a good segment. This implies that $\delta_{1}$ and $\delta_{2}$ are represented in $G$ by vertices of degree 1. Moreover, it is easy to see that at most one of them is a good triangle. Thus, at least $k-1$ vertices of degree 1 are not good triangles. This implies that there are at most 1003 good triangles. We obtain a triangulation with 1003 good triangles by considering 1003 disjoint diagonals that each leave exactly 1 vertex on one side, and then 1000 other diagonals to complete the triangulation.