# Triangulation of polygons, Whitehead moves, and associahedron

To triangulate a polygon means to cut it into triangles by diagonals. Let us assume that the polygon is convex, which means it may as well be the regular n-gon. There is nothing to do if n=3 (it’s already a triangle), so we begin with n=4. There are two ways to cut a square with a diagonal… well that wasn’t much to say.

Next, n=5. There are five ways to triangulate a pentagon: just choose a vertex and draw two diagonals starting from it. Actually, the number of triangulations of any convex n-gon is the kth Catalan number $C_k=frac{1}{k+1}binom{2k}{k}$ with $k=n-2$. With $k=5-2=3$ we get 5 as expected.

But we should do something beyond counting. A basic operation that one can perform on a triangulation is to remove one diagonal and replace it with another one (the choice of replacement is unique). This is called a Whitehead move. We can draw a graph in which vertices represent triangulations and edges correspond to Whitehead moves. Doing this for a pentagon gives… a pentagon. Funny.

Note that any triangulation of an n-gon involves exactly $k-1=n-3$ diagonals. Hence, there are $k-1$ possible Whitehead moves for any triangulation. This means that each vertex in our graph will have $k-1$ neighbors; in mathematical terms the degree of each vertex is $k-1$. As a consequence, the graph has $(k-1) C_k /2$ edges.

The case $n=6$ yields this pretty graph.

Is there a natural way to color the vertices, for any $n$? What is the chromatic number anyway? But it’s getting late.