Why is the maximum number of $K_3$ in a planar graph with $n$ vertices $3n-8$?

Question

According to Wikipedia, the maximum planar graphs are Apollonian networks.

It is said that the number of $K_3$ inside an Apollonian network is $3n-8$:

In extremal graph theory, Apollonian networks are also exactly the $n$-vertex planar graphs in which the number of blocks achieves its maximum, $n − 3$, and the planar graphs in which the number of triangles achieves its maximum, $3n − 8$. "

Why? What is the proof of that? How was it discovered?

Answer 1

[Edited after Perry's constructive comment] First a simple proof that only works for Apollonian networks. It is based on the recursive definition found on the WIKI:

An Apollonian network may be formed, starting from a single triangle embedded in the Euclidean plane, by repeatedly selecting a triangular face of the embedding, adding a new vertex inside the face, and connecting the new vertex to each vertex of the face containing it. In this way, the triangle containing the new vertex is subdivided into three smaller triangles, which may in turn be subdivided in the same way.

This yields a proof by induction. The statement is true for the 'first generation' ($n=3$), since $3n-8=9-8=1$. Assuming $n>3$ and the truth of the statement for smaller $n$, the addition of one new vertex inside a face adds exactly 3 $K_3$'s. By the induction hypothesis the previous generation has $3(n-1)-8$ $K_3$'s, so the new one has $3(n-1)-8+3=3n-8$ $K_3$'s.

Then a slightly more complicated proof for maximal planar graphs. Exclamation marks indicate spots where you may want to add evidence. Again we use induction, the base case ($n=3$) still being trivial.

For the induction step let $G$ be our graph with $n\geq 4$ vertices. We note that the outermost triangle is always a triangular face, since it bounds the unbounded face. If all its $K_3$'s are triangular faces, then the number of $K_3$'s equals the number of triangles, which is $2n-4$(!) $\leq 3n-8$ for $n\geq 4$.

So now assume $G$ has a $K_3$ that is not a triangular face, call it $C$. We split $G$ in two parts: $G_1$ being $C$ and its inside and $G_2$ being $C$ and its outside. Both parts are still maximal planar(!). If $G_1$ has $k$ vertices, then $G_2$ has $n-k+3$ vertices. With the exception of $C$ any $K_3$ of $G$ must be entirely within $G_1$ or entirely within $G_2$(!). Using the induction hypothesis we find that the number of $K_3$'s in $G$ is at most $(3k-8)+(3(n-k+3)-8)-1=3n-8$.

Answer 2

Your answer should be in the following reference:

S.L. Hakimi, E. F. Schmeichel. On the number of cycles of length $k$ in a maximal planar graph. J. Graph Theory 3 (1): 69-86.

http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190030108/abstract

I should also point out that Apollonian networks are not equivalent to maximal planar graphs. An Apollonian network is maximal planar, but not all maximal planar graphs are Apollonian networks. For example, the icosehedral graph is a maximal planar graph, but is not an Apollonian network.