A007816 -id:A007816 - cp's OEIS frontend

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

N. J. A. Sloane

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

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).

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

Cf. A005964, A007816, A058378, A253882.

Cf. A000944, A007021, A111358.

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)

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

Definition clarified by Manfred Scheucher, Mar 17 2023

A288265 Triangle read by rows: T(n,k) is the number of labeled connected planar graphs on n vertices and k edges.

Original entry on oeis.org

1, 1, 3, 1, 16, 15, 6, 1, 125, 222, 205, 120, 45, 10, 1296, 3660, 5700, 6165, 4935, 2937, 1125, 195, 16807, 68295, 156555, 258125, 330456, 334530, 254275, 131985, 40950, 5712, 262144, 1436568, 4483360, 10230360, 18528216, 27261192, 31761744, 27958920, 17666320, 7513632, 1922760, 223440, 4782969, 33779340, 136368414, 405918324, 970196283, 1910996136, 3058785990, 3866563764, 3754432899, 2724326136, 1425385584, 507370500, 109907280, 10929600

Offset: 1

Gheorghe Coserea, Aug 14 2017

Row n >= 3 contains 3*n-5 terms.

			A(x;t) = x + t*x^2/2! + (3*t^2 + t^3)*x^3/3! + (16*t^3 + 15*t^4 + 6*t^5 + t^6)*x^4/4! + ...
Triangle starts:
n\k [0] [1] [2] [3] [4]  [5]   [6]   [7]   [8]   [9]   [10]  [11]  [12]
[1] 1;
[2] 0   1;
[3] 0,  0,  3,  1;
[4] 0,  0,  0,  16, 15,  6,    1;
[5] 0,  0,  0,  0,  125, 222,  205,  120,  45,   10;
[6] 0,  0,  0,  0,  0,   1296, 3660, 5700, 6165, 4935, 2937, 1125, 195;
[7] ...

Gheorghe Coserea, Rows n = 1..126, flattened
E. A. Bender, Z. Gao and N. C. Wormald, The number of labeled 2-connected planar graphs, Electron. J. Combin., 9 (2002), #R43.
M. Bodirsky, C. Groepl and M. Kang, Generating Labeled Planar Graphs Uniformly At Random, Theoretical Computer Science, Volume 379, Issue 3, 15 June 2007, Pages 377-386.
Omer Gimenez, Marc Noy, Asymptotic enumeration and limit laws of planar graphs, J. Amer. Math. Soc. 22 (2009), 309-329.

Cf. A000272, A007816, A096332, A100960, A266390, A267411, A288266, A290326.

Q(n,k) = { \\ c-nets with n-edges, k-vertices
  if (k < 2+(n+2)\3 || k > 2*n\3, return(0));
  sum(i=2, k, sum(j=k, n, (-1)^((i+j+1-k)%2)*binomial(i+j-k,i)*i*(i-1)/2*
  (binomial(2*n-2*k+2,k-i)*binomial(2*k-2, n-j) -
  4*binomial(2*n-2*k+1, k-i-1)*binomial(2*k-3, n-j-1))));
};
A100960_ser(N) = {
my(x='x+O('x^(3*N+1)), t='t+O('t^(N+4)),
   q=t*x*Ser(vector(3*N+1, n, Polrev(vector(min(N+3, 2*n\3), k, Q(n,k)),'t))),
   d=serreverse((1+x)/exp(q/(2*t^2*x) + t*x^2/(1+t*x))-1),
   g2=intformal(t^2/2*((1+d)/(1+x)-1)));
   serlaplace(Ser(vector(N, n, subst(polcoeff(g2, n,'t),'x,'t)))*'x);
};
A288265_ser(N) = {
  my(x='x+O('x^(N+3)), b = t*x^2/2 + serconvol(A100960_ser(N), exp(x)),
     g1=intformal(serreverse(x/exp(b'))/x)); serlaplace(g1);
};
A288265_seq(N) = {
  my(v=Vec(A288265_ser(N))); vector(#v, n, Vecrev(v[n]/t^(n-1)));
};
concat(A288265_seq(9))

A096332(n) = Sum_{k=n-1..3*n-6} T(n,k) for n >= 3.

A000272(n) = T(n,n-1), A007816(n-3) = T(n, 3*n-6).

A288266 Triangle read by rows: T(n,k) is the number of labeled planar graphs on n vertices and k edges.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 3, 1, 1, 6, 15, 20, 15, 6, 1, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 4995, 2937, 1125, 195, 1, 21, 210, 1330, 5985, 20349, 54264, 116280, 203490, 293860, 351225, 342405, 255640, 131985, 40950, 5712, 1, 28, 378, 3276, 20475, 98280, 376740, 1184040, 3108105, 6906620, 13112694, 21322812, 29332947, 32823084, 28286520, 17712016, 7513632, 1922760, 223440

Offset: 0

Gheorghe Coserea, Aug 14 2017

Row n >= 3 contains 3*n-5 terms.

			A(x;t) = 1 + x + (1+t)*x^2/2! + (1+3*t+3*t^2+t^3)*x^3/3! + (1+6*t+15*t^2+20*t^3+15*t^4+6*t^5+t^6)*x^4/4! + ...
Triangle starts:
n\k [0] [1] [2]  [3]  [4]   [5]   [6]   [7]   [8]   [9]   [10]  [11]  [12]
[0] 1;
[1] 1;
[2] 1   1;
[3] 1,  3,  3,   1;
[4] 1,  6,  15,  20,  15,   6,    1;
[5] 1,  10, 45,  120, 210,  252,  210,  120,  45,   10;
[6] 1,  15, 105, 455, 1365, 3003, 5005, 6435, 6435, 4995, 2937, 1125, 195;
[7] ...

Gheorghe Coserea, Rows n = 0..126, flattened
E. A. Bender, Z. Gao and N. C. Wormald, The number of labeled 2-connected planar graphs, Electron. J. Combin., 9 (2002), #R43.
M. Bodirsky, C. Groepl and M. Kang, Generating Labeled Planar Graphs Uniformly At Random, Theoretical Computer Science, Volume 379, Issue 3, 15 June 2007, Pages 377-386.
Omer Gimenez, Marc Noy, Asymptotic enumeration and limit laws of planar graphs, J. Amer. Math. Soc. 22 (2009), 309-329.

Cf. A096332, A100960, A266390, A288265, A290326.

Q(n,k) = { \\ c-nets with n-edges, k-vertices
  if (k < 2+(n+2)\3 || k > 2*n\3, return(0));
  sum(i=2, k, sum(j=k, n, (-1)^((i+j+1-k)%2)*binomial(i+j-k,i)*i*(i-1)/2*
  (binomial(2*n-2*k+2,k-i)*binomial(2*k-2, n-j) -
  4*binomial(2*n-2*k+1, k-i-1)*binomial(2*k-3, n-j-1))));
};
A100960_ser(N) = {
my(x='x+O('x^(3*N+1)), t='t+O('t^(N+4)),
   q=t*x*Ser(vector(3*N+1, n, Polrev(vector(min(N+3, 2*n\3), k, Q(n,k)),'t))),
   d=serreverse((1+x)/exp(q/(2*t^2*x) + t*x^2/(1+t*x))-1),
   g2=intformal(t^2/2*((1+d)/(1+x)-1)));
   serlaplace(Ser(vector(N, n, subst(polcoeff(g2, n,'t),'x,'t)))*'x);
};
A288266_seq(N) = {
  my(x='x+O('x^(N+3)), b=t*x^2/2 + serconvol(A100960_ser(N), exp(x)),
     g1=intformal(serreverse(x/exp(b'))/x));
  apply(p->Vecrev(p), Vec(serlaplace(exp(g1))));
};
concat(A288266_seq(8))

A066537(n) = Sum_{k=0..3*n-6} T(n,k) for n >= 3.

A007816(n-3) = T(n, 3*n-6).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A288265 Triangle read by rows: T(n,k) is the number of labeled connected planar graphs on n vertices and k edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A288266 Triangle read by rows: T(n,k) is the number of labeled planar graphs on n vertices and k edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula