# Upper bound on the number of triangles in a planar graph

For any $n \geq 4$, I was able to prove that every Apollonian network has $3n - 8$ triangles. An Apollonian network is a planar graph defined by recursively subdividing a triangle by three smaller triangles (adding a new vertex inside the face and connecting it to all three vertices). Now I am trying to prove a similar statement for arbitrary planar graphs. In particular, I am trying to show that every planar graph has at most $an + b$ triangles, for some constants $a$ and $b$, where the goal is to make the constants as tight as possible. The result I showed implies that we need $a \geq 3$ and $b \geq -8$ This is an assignment question, so I would only like a hint please. I believe that I should be able to prove that no planar graph has more triangles than an Apollonian network, but unsure how to proceed.

• Welcome to CS.SE! This looks like a pure math question, and so more suitable for Math.SE. If you agree, please click "flag" to flag it for moderator attention and ask the moderators to migrate it. (But don't re-post/cross-post, as that's frowned upon.) Alternatively, if you see a reason why this needs to be answered from a computer science perspective, please edit the question to articulate why. – D.W. Nov 1 '15 at 7:21
• It doesn't show that $b \geq -8$. You could have $100n - 10$, for example, which is also a valid upper bound. – Yuval Filmus Nov 1 '15 at 7:30