Given a simple ngon a How many triangles in a diagonal trian

Given a (simple) n-gon. a. How many triangles in a diagonal triangulation of the n-gon b. Prove that there are n-3 diagonals in a diagonal triangulation of the n-gon. Reconstruct the tree T with the Prufer code a. 123 b. 31413

Solution

a)

Every triangulation of an n-gon has (n-2)-triangles.

b)

The proof is based on the existence of a (diagonal) triangulation of polygons: every polygon can be split into triangles by some of its diagonals.

We first establish a preliminary result:

Every triangulation of an n-gon has (n-2)-triangles formed by (n-3) diagonals.

The proof is by induction. If n = 3, the assertion is trivially true.

Assume the statement holds for all n < K. Given a K-gon, find - as in the proof of the existence of a triangulation - a diagonal that splits the polygon into smaller two, say n-gon and m-gon such that n + m = K + 2 and both are less than K.

Then, by the induction hypothesis, the n-gon consists of (n-2) triangles, while the m-gon consists of (m-2) triangles. In all, there are

(n - 2) + (m - 2) = (K + 2) - 4 = K - 2

triangles, as required. The number of the diagonals is

(n - 3) + (m - 3) + 1 = K + 2 - 5 = K - 3.