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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ 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. $\endgroup$– D.W. ♦Nov 1, 2015 at 7:21
-
$\begingroup$ It doesn't show that $b \geq -8$. You could have $100n - 10$, for example, which is also a valid upper bound. $\endgroup$– Yuval FilmusNov 1, 2015 at 7:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Presumably you have to show that if you triangulate an arbitrary planar graph then you get an Apollonian network. Then you have to show that the triangulated graph contains more triangles than the original one. This will complete the proof.
answered Nov 1, 2015 at 7:30
-
$\begingroup$ Thanks! The strategy you suggested work for proving the result I wanted. $\endgroup$– user41814Nov 2, 2015 at 3:32