Problem 2

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 composed of an odd number of sides of

P

. The sides of

P

are also called good. Suppose

P

has been dissected into triangles by

2003

diagonals, no two of which have a common point in the interior of

P

. Find the maximum number of isosceles triangles having two good sides that could appear in such a configuration.

Step 3 of 5: Count the leaves of the forest

Previous step Next step

In plain words

A triangle with two good sides becomes a leaf after good-diagonal edges are removed; a triangle with no good side keeps all three non-good diagonal adjacencies. A tree whose degrees are only $1$ and $3$ has $(n_i+2)/2$ leaves.

\deg_F(v)\in\{1,3\},\qquad L(F)=\sum_{i=1}^{k+1}\frac{n_i+2}{2}=1003+k

Detailed analysis

By Step 1, every triangle has two good sides or zero. Boundary sides are good, so a zero-good-side triangle has three non-good diagonals and degree $3$ in $F$ , while a two-good-side triangle has exactly one non-good side and degree $1$ . If the $k+1$ components have $n_1,\ldots,n_{k+1}$ vertices, the $i$ th has $(n_i+2)/2$ leaves. Since $\sum n_i=2004$ , $F$ has $1003+k$ leaves.