Page 360 - Discrete Mathematics and Its Applications

5.2 Strong Induction and Well-Ordering 339

Two different triangulations of a simple polygon with seven sides into five triangles,
shown with dotted lines and with dashed lines, respectively

FIGURE 2 Triangulations of a Polygon.

polygon, as we state in Theorem 1. Furthermore, this theorem tells us that every triangulation
of a simple polygon with n sides includes n − 2 triangles.

THEOREM 1 A simple polygon with n sides, where n is an integer with n ≥ 3, can be triangulated into
n − 2 triangles.

It seems obvious that we should be able to triangulate a simple polygon by successively
adding interior diagonals. Consequently, a proof by strong induction seems promising. However,
such a proof requires this crucial lemma.

LEMMA 1 Every simple polygon with at least four sides has an interior diagonal.

Although Lemma 1 seems particularly simple, it is surprisingly tricky to prove. In fact, as
recently as 30 years ago, a variety of incorrect proofs thought to be correct were commonly seen
in books and articles. We defer the proof of Lemma 1 until after we prove Theorem 1. It is not
uncommon to prove a theorem pending the later proof of an important lemma.

Proof (of Theorem 1): We will prove this result using strong induction. Let T (n) be the
statement that every simple polygon with n sides can be triangulated into n − 2 triangles.

BASIS STEP: T(3) is true because a simple polygon with three sides is a triangle.We do not need
to add any diagonals to triangulate a triangle; it is already triangulated into one triangle, itself.
Consequently, every simple polygon with n = 3 has can be triangulated into n − 2 = 3 − 2 = 1
triangle.
INDUCTIVE STEP: For the inductive hypothesis, we assume that T(j) is true for all
integers j with 3 ≤ j ≤ k. That is, we assume that we can triangulate a simple polygon
with j sides into j − 2 triangles whenever 3 ≤ j ≤ k. To complete the inductive step, we
must show that when we assume the inductive hypothesis, P(k + 1) is true, that is, that every
simple polygon with k + 1 sides can be triangulated into (k + 1) − 2 = k − 1 triangles.
So, suppose that we have a simple polygon P with k + 1 sides. Because k + 1 ≥ 4, Lemma 1
tells us that P has an interior diagonal ab.Now, ab splits P into two simple polygons Q, with
s sides, and R, with t sides. The sides of Q and R are the sides of P, together with the side
ab, which is a side of both Q and R. Note that 3 ≤ s ≤ k and 3 ≤ t ≤ k because both Q
and R have at least one fewer side than P does (after all, each of these is formed from P
by deleting at least two sides and replacing these sides by the diagonal ab). Furthermore, the
number of sides of P is two less than the sum of the numbers of sides of Q and the number of