Show triangulations can be transformed into each other by edge flip. Let $\Delta_1$ and $\Delta_2$ be two triangulations of the same point set $P_n$. Show that they can be transformed into each other by edge flips. To define an edge flip, let $pqrs$ be vertices (in clockwise order) of a quadrilateral. If $pr$ is an edge in the triangulation, then $pr$ can be flipped into $qs$.
For convex polygon case, it is easy to show there exists a sequence of edge flip that will increase the number of common edges of two different triangulations. But I am stuck in the general case. Any hint? 
 A: Another way to show this is by using the optimization properties of the Delaunay triangulation, which are treated e.g. in this paper (Section 4.2) and this presentation. Call an edge of a triangulation locally Delaunay if it is part of the convex hull or if the circumcircle of neither triangle containing it contains the third vertex of the other triangle containing it. Then any edge that isn't locally Delaunay can be replaced through an edge flip by one that is. Also, if we order the triangulations by forming the vector of vertex angles (all triangulations have the same number of triangles and thus of vertex angles), sorting it in ascending order and using the lexicographical order on these sorted vectors, the edge flips increase the triangulation with respect to this order, since they increase the minimal angle in the triangles containing them. Thus the process must terminate with a triangulation in which all edges are locally Delaunay. This implies the global Delaunay properties, and thus the resulting triangulation is a Delaunay triangulation. Any Delaunay triangulation can be transformed into any other Delaunay triangulation using edge flips in the convex polygons around Voronoi vertices equidistant from more than three points. (Alternatively, slightly perturb the points to bring them into general position to make the Delaunay triangulation unique and thus avoid this special case.) Thus, there is a sequence of edge flips from $\Delta_1$ to a Delaunay triangulation to another Delaunay triangulation and back to $\Delta_2$ (using the inverse of the sequence of edge flips required to turn $\Delta_2$ into a Delaunay triangulation).
A: I think the problem is solved in Hurtado, Noy, and Urrutia, Flipping edges on triangulations, at http://www.matem.unam.mx/urrutia/online_papers/Flipping.pdf
