Largest 4 ‐connected components of 3 ‐connected planar triangulations
Edward A. Bender, L. Bruce Richmond, Nicholas Wormald · Random Structures and Algorithms · 1995
Abstract Let T n be a 3‐connected n ‐vertex planar triangulation chosen uniformly at random. Then the number of vertices in the largest 4‐connected component of T n is asymptotic to n /2 with probability tending to 1 as n → ∞. It follows that almost all 3‐connected triangulations with n vertices have a cycle of length at least n /2 + o(n) .