Before revision:  Our methods yield further results for regular triangulations. Among others, we show that there are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction) .
After revision:  For the edge flip-graphs, the vertex connectivity can be shown to be at least as large as (and hence equal to) the minimum degree, provided n is large enough. Our methods yield several other results .