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 2 of 5: Delete good diagonals from the triangulation tree

Previous step Next step

In plain words

The $2004$ triangles are nodes of a tree, with an edge when two triangles share a diagonal. Removing the $k$ good diagonals splits this tree into $k+1$ components.

T=\text{dual tree of the triangulation},\qquad F=T\setminus\{\text{edges for good diagonals}\}

Detailed analysis

The dual graph $T$ of a polygon triangulation is a tree with $2004$ vertices. Let $k$ be the number of good diagonals used. Deleting the corresponding $k$ edges gives a forest $F$ with $k+1$ trees.