A296515 Number of edges in a maximal planar graph with n vertices.

0, 0, 1, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174

Offset: 0

Author

Joseph Wheat, Jonathan Sondow, Feb 28 2018

Keywords

• nonn
• easy

Comments

{a(n)} is a monotonic increasing sequence because a maximal planar graph of order n can be generated on n + 1 nodes. Therefore a(n) <= a(n + 1).

Maximal planar graphs of order n > 5 are not unique.

|E(G_2n)| = (2n - 1) + 2*Sum_{k=0..(floor(log_2(n - 1)))} floor((n - 1)/2^k) where |E(G_2n)| is the size of a minimal planar graph G of order 2n.

Number of edges of a maximal 3-degenerate graph of order n (this class includes 3-trees). The intersection of this class and maximal planar graphs is the Apollonian networks (planar 3-trees); neither class contains the other. - Allan Bickle, Nov 14 2021

a(n) is the number of blocks to dig (in a staircase fashion) to get out of a hole of depth n in Minecraft. - Max R Anderson, Oct 19 2023

Links

• Stefano Spezia, Table of n, a(n) for n = 0..10000
• Allan Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 4 (2012), 659-676.
• Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
• Dawei He, Yan Wang, and Xingxing Yu, The Kelmans-Seymour conjecture I, arXiv:1511.05020 [math.CO], 2015.
• D. R. Lick and A. T. White, k-degenerate graphs, Canad. J. Math. 22 (1970), 1082-1096.
• Mathematics Stack Exchange, You dig a hole in Minecraft straight down n blocks, how many blocks must you dig to get out?
• K. Stephenson, Circle Packing: A Mathematical Tale, Notices Amer. Math. Soc. 50 (2003).
• Squid Tamar-Mattis, Planar Graphs and Wagner's and Kuratowski's Theorems, REU (2016).
• Eric Weisstein's World of Mathematics, Kuratowski Reduction Theorem, Polyhedral Graph
• David R. Wood, A Simple Proof of the Fary-Wagner Theorem, arXiv:cs/0505047 [math.CO], 2005.
• Index entries for linear recurrences with constant coefficients, signature (2,-1).

Crossrefs

Cf. A008486, A008585, A242088.

Programs

Mathematica

CoefficientList[Series[(x^2 (1 + x + x^2))/(x - 1)^2, {x, 0, 60}], x] (* or *) LinearRecurrence[{2, -1}, {0, 0, 1, 3}, 60] (* Robert G. Wilson v, Mar 04 2018 *)

Formula

a(n) = floor(6/2^n) + 3n - 6 (see comments section of A008486).

G.f.: x^2 + 3*x^3/(x - 1)^2. - R. J. Mathar, Apr 14 2018

E.g.f.: 6 + x*(x + 6)/2 + 3*exp(x)*(x - 2). - Stefano Spezia, Feb 13 2023

a(n) = 3*(n - 2) for n >= 3. - Max R Anderson, Oct 19 2023