On the Maximum Degree of a Random Planar Graph. - McDiarmid, C; Reed, B (2008)
Let the random graph Rn be drawn uniformly at random from the set of all simple planar graphs on n labelled vertices. We see that with high probability the maximum degree of Rn is ⊖(ln n). We consider also the maximum size of a face and the maximum increase in the number of components on deleting a vertex. These results extend to graphs embeddable on any fixed surface. © 2008 Cambridge University Press.