Prove that any two triangulations of a convex polygon can be transformed into each other by a sequence of edge flips.

Question

I saw a similar questuion here Show triangulations can be transformed into each other by edge flip. asked 8 years ago. It claimed that it is easy to show there exists a sequence of edge flip that will increase the number of common edges of two different triangulations of a convex polygon, but I still cannot figure out how. Any hint? Thank you in advance.

Answer 1

Flipping an edge is a reversible process, so if we show that any triangulation $T$ can reach a specific fixed $T_0$ by flipping, then to reach $T'$ from $T$, go from $T$ to $T_0$, then back in reverse from $T_0$ to $T'$.

As a choice for $T_0$, we could take the "scallop" triangulation, where all edges connect to a single vertex. To reach this from any $T$, we can do the following: if less than $n-3$ edges connect to our vertex $v_0$, we may find an edge that is internal, and flip it to increase the number of edges connected to $v_0$.

To justify why we can always find such an edge to flip that increases this is an obvious fact geometrically, and to justify this rigorously we could use that the number of triangles in the triangulation is independent of the triangulation, so less than $n-3$ edges connecting to $v_0$ yields a proper subset of the triangles. If this last bit is unclear, you should draw the pictures to convince yourself that this geometric fact is obvious.