Theorem:  Any polygon can be decomposed into triangles.

Proof: The key idea of the proof goes by the method of mathematical induction. Let n = the number vertices = the number of sides in the polygon. 

The induction starts by considering n=3. Then we assume that we have justified the result for polygons with k vertices where k<n and justify the result for n based on this assumption. This allows us to use "induction" to prove the result for any value of n. Starting with n=3, we have the result is true for n= 4, and then n=5, and then n=6,.... and we can continue to any specific value of n.

Case 1

Case 2

Case 3. The vertex is vk with k different from 3 or n. Then consider the polygonal regions Q3 = v1v2...vk which has k vertices (k<n) and Q4 = which has n-(k-2)<n vertices.

By induction Q3 and Q4 can be triangulated, so the original polygon is triangulated using the triangulations of Q3 and Q4.

Case 3
End of Proof.

For more discussion of proofs of this proposition see Triangulations and arrangements, Two lectures by Godfried Toussaint, transcribed by Laura Anderson and Peter Yamamoto.