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 with . With 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 diagonals. Hence, there are possible Whitehead moves for any triangulation. This means that each vertex in our graph will have neighbors; in mathematical terms the degree of each vertex is . As a consequence, the graph has edges.
The case yields this pretty graph.
Note that there are no triangles in this graph. There can’t be any, because two subsequent Whitehead moves result in removal of two diagonals, and this can’t be undone in one move. So, the shortest cycle has length 4. Looking closely at the faces (some with 4 vertices, some with 5) you notice that all their triangulations have one diagonal in common. The faces can actually be represented by polygons, making the graph into a polytope known as an associahedron:
Is there a natural way to color the vertices, for any ? What is the chromatic number anyway? But it’s getting late.