Competition problem — Combinatorics

Library / /83 of 94

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:
Let $n \geq 3$ be a positive integer. A triangulation of a convex $n$ -gon is a set of $n-3$ of its diagonals which do not intersect in the interior of the polygon. Along with the $n$ sides, these diagonals separate the polygon into $n-2$ disjoint triangles. Any triangulation can be viewed as 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 of these graphs have the same chromatic number.

Solution

Solution:
We will show that all triangulations have chromatic number $3$ , by induction on $n$ .

As a base case, if $n=3$ , a triangle has chromatic number $3$ .

Now, given a triangulation of an $n$ -gon for $n>3$ , every edge is either a side or a diagonal of the polygon. There are $n$ sides and only $n-3$ diagonals in the edge-set, so the Pigeonhole Principle guarantees a triangle with two side edges. These two sides must be adjacent, so we can remove this triangle to leave a 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 this vertex with one of the three colors not used on its neighbors.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.