On random planar graphs, the number of planar graphs and their triangulations

Let Pn be the set of labelled planar graphs with n vertices. Denise, Vasconcellos and Welsh proved that |Pn|⩽n! (75.8)n+o(n) and Bender, Gao and Wormald proved that |Pn|⩾n! (26.1)n+o(n). Gerke and McDiarmid proved that almost all graphs in Pn have at least 13/7n edges. In this paper, we show that |Pn|⩽n! (37.3)n+o(n) and that almost all graphs in Pn have at most 2.56n edges. The proof relies on a result of Tutte on the number of plane triangulations, the above result of Bender, Gao and Wormald and the following result, which we also prove in this paper: every labelled planar graph G with n vertices and m edges is contained in at least ε3(3n−m)/2 labelled triangulations on n vertices, where ε is an absolute constant. In other words, the number of triangulations of a planar graph is exponential in the number of edges which are needed to triangulate it. We also show that this bound on the number of triangulations is essentially best possible.