HMMT 二月 2009 · TEAM2 赛 · 第 3 题

英文解析

3. [ 8 ] Let n ≥ 3 be a positive integer. A triangulation of a convex n -gon is a set of n − 3 of itsdiagonals which do not intersect in the interior of the polygon. Along with the n sides, thesediagonals separate the polygon into n − 2 disjoint triangles. Any triangulation can be viewedas a graph: the vertices of the graph are the corners of the polygon, and the n sides and n − 3
   diagonals are the edges.
   For a fixed n -gon, different triangulations correspond to different graphs. Prove that all ofthese graphs have the same chromatic number.
   Solution: We will show that all triangulations have chromatic number 3, by induction onn . As a base case, if n = 3, a triangle has chromatic number 3. Now, given a triangulation ofan n -gon for n > 3, every edge is either a side or a diagonal of the polygon. There are n sidesand only n − 3 diagonals in the edge-set, so the Pigeonhole Principle guarentees a trianglewith two side edges. These two sides must be adjacent, so we can remove this triangle to leavea triangulation of an n − 1-gon, which has chromatic number 3 by the inductive hypothesis.
   Adding the last triangle adds only one new vertex with two neighbors, so we can color thisvertex with one of the three colors not used on its neighbors.