Now, we are ready to formalize the notion of a polygon triangulation. Let P be a polygon with n vertices. Triangulation of P is partitioned into triangles by a maximum set of pairwise non-intersecting diagonals. Here we mean maximality by inclusion. In a sense that no other diagonal of P can be added to the set of already selected ones, unless it intersects some of those. In the slide on the left you see an example of a polygon P along with its triangulation. It is easy to see that in general, triangulation of a polygon is not unique. For example, we may modify the triangulation from the example you have just seen on the previous slide. To the same, let us pickup the diagonal now labeled in light gray, and replace it with the one labeled in red. In this way, we will get another triangulation of the polygon P. Now let us prove the following important property. Any polygon admits a triangulation. For a polygon P with n vertices, any its triangulation has n minus three diagonals and n minus two triangles. In particular, in this course for our example, you now see on the left. Our polygon has seven vertices, the triangulation presented here has four diagonals, and it comprises five triangles. It is easy to see that both relations hold. We will prove our claim by induction. The induction base will be a triangle. A triangle has three vertices, and it represents by itself its own triangulation. Thus for triangulation, we need no or zero diagonals, and the number of triangles in this triangulation is one. For this case, the claim trivial holds. According to the induction hypothesis, our claim should hold for any polygon with number of vertices n smaller than k. Now, let us prove our claim for n equal to k. Let P be a polygon with k vertices. According to the lemma we proved earlier, the polygon P has a diagonal. Let us pick up some diagonal of P, which we'll denote by ab. The diagonal ab split the polygon P into two polygons P_1 and P_2, with the number of vertices k_1 and k_2 respectively. Since k_1 and k_2 are smaller than k, both P_1 and P_2 admit a triangulation, which possesses these specified properties. Let us pick up some triangulations of P_1 and P_2. The set of diagonals of those triangulations along with the diagonal ab, define triangulation of the polygon P. Now let us calculate the number of diagonals in the triangulation of P we obtained. The number of those in the triangulation of P_1 which we used, by the diagonal hypothesis equals k_1 minus three. Similarly, the number of those in the triangulation of P_2 equals k_2 minus three, and in addition, we should account for the diagonal ab. Note that having summed up k_1 and k_2, we will get k plus two. This is because in this way, we account for each vertex of P except for a and b precisely ones. While each of a and b will be counted twice, once for P_1 and once for P_2. To calculate the number of triangles in the triangulation of P, we should follow precisely the same scheme. The number of those in the triangulation of P_1 equals k_1 minus two by the induction hypothesis, and similarly the number of those in the triangulation of P_2 equals k_2 minus two. Altogether, those triangles represent the set of triangles from the triangulation of P, and their total number equals k plus two minus four or k minus two, which finalizes our proof. It remains to justify the second claim of our lemma, and then it demonstrated that any triangulation of the polygon P has n minus three diagonals, and n minus two triangles. This can be shown by induction in a fully analogous way.
