A000109 Number of simplicial polyhedra with n vertices; simple planar graphs with n vertices and 3n-6 edges; maximal simple planar graphs with n vertices; planar triangulations with n vertices; triangulations of the sphere with n vertices; 3-connected cubic planar graphs on 2n-4 vertices.

1, 1, 1, 2, 5, 14, 50, 233, 1249, 7595, 49566, 339722, 2406841, 17490241, 129664753, 977526957, 7475907149, 57896349553, 453382272049, 3585853662949, 28615703421545

Offset: 3

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• hard
• more
• core
• changed

Comments

Every planar triangulation on n >= 4 vertices is 3-connected (the connectivity either 3, 4, or 5) and its dual graph is a 3-connected cubic planar graph on 2n-4 vertices. - Manfred Scheucher, Mar 17 2023

References

• G. Brinkmann and Brendan McKay, in preparation. [Looking at http://users.cecs.anu.edu.au/~bdm/publications.html, there are a few papers with Brinkmann that seem relevant, in particular #126 but also #97, 81, 158. Perhaps the right one is 126.]
• M. B. Dillencourt, Polyhedra of small orders and their Hamiltonian properties. Tech. Rep. 92-91, Info. and Comp. Sci. Dept., Univ. Calif. Irvine, 1992.
• C. F. Earl and L. J. March, Architectural applications of graph theory, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979.
• B. Grünbaum, Convex Polytopes. Wiley, NY, 1967, p. 424.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• David Wasserman, Table of n, a(n) for n = 3..23
• J. Bokowski and P. Schuchert, Equifacetted 3-spheres as topes of nonpolytopal matroid polytopes, Discrete Comput. Geom. 13 (1995), no. 3-4, 347-361.
• R. Bowen and S. Fisk, Generation of triangulations of the sphere [Annotated scanned copy]
• R. Bowen and S. Fisk, Generation of triangulations of the sphere, Math. Comp., 21 (1967), 250-252.
• Gunnar Brinkmann and Brendan McKay, plantri and fullgen programs for generation of certain types of planar graph.
• Gunnar Brinkmann and Brendan McKay, plantri and fullgen programs for generation of certain types of planar graph [Cached copy, pdf file only, no active links, with permission]
• CombOS - Combinatorial Object Server, generate planar graphs
• Aharon Davidson, From Planck Area to Graph Theory: Topologically Distinct Black Hole Microstates, arXiv:1907.03090 [gr-qc], 2019.
• M. Deza, M. Dutour and P. W. Fowler, Zigzags, railroads and knots in fullerenes, J. Chem. Inf. Comput. Sci., 44 (2004), 1282-1293.
• C. F. Earl and L. J. March, Architectural applications of graph theory, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979. (Annotated scanned copy)
• P. J. Federico, Enumeration of polyhedra: the number of 9-hedra, J. Combin. Theory, 7 (1969), 155-161.
• Firsching, Moritz Realizability and inscribability for simplicial polytopes via nonlinear optimization. Math. Program. 166, No. 1-2 (A), 273-295 (2017). Table 1
• Komei Fukuda, Hiroyuki Miyata, and Sonoko Moriyama, Complete Enumeration of Small Realizable Oriented Matroids. Discrete Comput. Geom. 49 (2013), no. 2, 359--381. MR3017917. Also arXiv:1204.0645 [math.CO], 2012. - From _N. J. A. Sloane_, Feb 16 2013
• Jan Goedgebeur and Patric R. J. Ostergard, Switching 3-Edge-Colorings of Cubic Graphs, arXiv:2105:01363 [math.CO], May 2021. See Table 4.
• R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
• Lee Zheng Han and Chia Vui Leong, The Walk of Maximal Planar Graphs, 2018.
• Jorik Jooken, Computer-assisted graph theory: a survey, arXiv:2508.20825 [math.CO], 2025. See p. 5.
• Paul Jungeblut, Edge Guarding Plane Graphs, Master Thesis, Karlsruhe Institute of Technology (Germany, 2019).
• J. Lederberg, Dendral-64, II, Report to NASA, Dec 1965 [Annotated scanned copy]
• J. Lederberg, Hamilton circuits of convex trivalent polyhedra (up to 18 vertices), Am. Math. Monthly, 74 (1967), 522-527.
• J. Lederberg, Hamilton circuits of convex trivalent polyhedra (up to 18 vertices), Am. Math. Monthly, 74 (1967), 522-527. (Annotated scanned copy)
• F. H. Lutz, Triangulated manifolds with few vertices: Combinatorial Manifolds, arXiv:math/0506372 [math.CO], 2005.
• G. P. Michon, Counting Polyhedra
• Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner, A Note On Universal Point Sets for Planar Graphs, arXiv:1811.06482 [math.CO], 2018.
• I. Sciriha and P. W. Fowler, Nonbonding Orbitals in Fullerenes: Nuts and Cores in Singular Polyhedral Graphs, J. Chem. Inf. Model., 47, 5, 1763 - 1775, 2007.
• A. Stoimenow, A theorem on graph embedding with a relation to hyperbolic volume, Combinatorica, October 2016, Volume 36, Issue 5, pp 557-589.
• Thom Sulanke, Generating triangulations of surfaces (surftri), (also subpages).
• William T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962), 21-38.
• William T. Tutte, On the enumeration of convex polyhedra, J. Combin. Theory Ser. B 28 (1980), 105-126.
• Eric Weisstein's World of Mathematics, Cubic Polyhedral Graph
• Eric Weisstein's World of Mathematics, Simple Polyhedron
• Eric Weisstein's World of Mathematics, Triangulated Graph
• Index entries for "core" sequences

Crossrefs

Cf. A005964, A007816, A058378, A253882.

Cf. A000944, A007021, A111358.

Formula

From William P. Orrick, Apr 07 2021: (Start)

a(n) >= A007816(n-3)/n! = binomial(n,2)*(4*n-11)!/(n!*(3*n-6)!) for all n >= 4.

a(n) ~ A007816(n-3)/n! = binomial(n,2)*(4*n-11)!/(n!*(3*n-6)!) ~ (1/64)*sqrt(1/(6*Pi))*n^(-7/2)*(256/27)^(n-2), using the theorem that the automorphism group of a maximal planar graph is almost certainly trivial as n gets large. (Tutte)

(End)

Extensions

Extended by Brendan McKay and Gunnar Brinkmann using their program "plantri", Dec 19 2000

Definition clarified by Manfred Scheucher, Mar 17 2023