What is the maximum number of triangles we can draw in a planar graph using at most 30 nodes and 50 edges

Question

I'm trying to solve this problem because I need to implement it into my program for calculating some values related to this.

Namely, I need to find what is the maximum number of triangles we can draw if we can use only up to 30 nodes and up to 50 edges. The triangles can share point, points or sides.

I started thinking if we can put one point in the center and then we put all the other points around it and then connect with the point in the center, but it looks like this wont be the maximum number.

Answer 1

Take the complete graph on 10 nodes. It needs ${10 \choose 2}=45$ edges. You get ${10 \choose 3}=120$ triangles. And you have 5 more edges.

Answer 2

I got 50 edges 19 nodes 32 triangles.

Answer 3

Let $T$ denote the number of triangles in such a graph, and $E$ the number of edges. Every triangle has precisely $3$ edges, and every edge is adjacent to at most $2$ triangles, so $3T\leq2E$. Given that $E\leq50$ it follows that $T\leq33$.

If $T=33$ then there is precisely one edge $e_0$ that is adjacent to precisely one triangle; every other edge is adjacent to precisely two triangles. But then the face that $e_0$ is adjacent to that is not a triangle has other edges adjacent to it (assuming the graph is simple), contradicting the fact that $e_0$ is the unique edge adjacent to a non-triangle. Hence $T<33$.

Examples of planar graphs with at most $30$ vertices and at most $50$ edges with $32$ triangular faces have already been given, so this is the maximum. The following sequence of planar graph gives another example:

The sixth graph in this sequence has $18$ vertices, $48$ edges and $32$ faces, all of which are triangular.

---

If the graph is not required to be simple, then the maximum number of triangles is in fact $33$. The following sequence of planar graphs yields an example:

The $n$-th graph has $V_n=2n+2$ vertices, $E_n=6n+2$ edges and $F_n=4n+2$ faces, of which $T_n=F_n-1=6n+1$ are triangular. So for $n=8$ we get a planar graph on $18$ vertices with $50$ edges and $34$ faces, of which $33$ are triangular. The argument above shows that this is maximal.