Explain why a convex ngon can be cut into n 2 trianglesSolu

Explain why a convex n-gon can be cut into n - 2 triangles.

Solution

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.

Now, for the proof of the main statement. Consider a triangulation of an n-gon, with n > 3. The triangulation consists of n-2 triangles. Each of the triangles in the triangulation shares at most 2 edges with the polygon. Since the latter has n edges but there are only two triangles, by the Pigeonhole Principle, there are at least two triangles with two polygon\'s edges. These are the ears.