The Art and Craft of Problem Solving

48 CHAPTER 2 STRATEGIES FOR INVESTIGATING PROBLEMS

Now our stronger inductive hypothesis allows us to use the truth of both P(u) and

P(u-l),so

au+l + (u - 1)^2 = 2u^2 + 2,

and hence

The previous example needed the truth of P( u) and P( u -I). The next example

uses the truth of P(k) for two arbitrary values.

Example 2.3.9 A partition of a set is a decomposition of the set into disjoint subsets.

A triangulation of a polygon is a partition of the polygon into triangles, all of whose

vertices are vertices of the original polygon. A given polygon can have many different

triangulations. Here are two different triangulations of a 9-gon.

Given a triangulation, call two vertices adjacent if they are joined by the edge of

a triangle. Suppose we decide to color the vertices of a triangulated polygon. How

many colors do we need to use in order to guarantee that no two adjacent vertices have

the same color? Certainly we need at least three colors, since that is required for just a

single triangle. The surprising fact is that

Three colors always suffice fo r any triangulation of a polygon!

Proof" We shall induct on n, the number of vertices of the polygon. The statement

P(n) that we wish to prove for all integers n 2: 3 is

For any triangulation of an n-gon, it is possible to 3-color the vertices

(i.e., color the vertices using three colors) so that no two adjacent ver­

tices are the same color.

The base case P(3) is obviously true. The inductive hypothesis is that

P(3),P(4), ... , P(n)

are all true. We will show that this implies P(n + 1 ). Given a triangulated (n + 1)­

gon, pick any edge and consider the triangle T with vertices x,y,z that contains this

edge. This triangle cuts the (n + 1 )-gon into two smaller triangulated polygons Land