A6

We use Euler's formula V-E+F=1, where V is the number of vertices, E the number of edges, and F the number of faces (down 1 because we do not count the outer one).

Notation:

deg(v): the degree of a vertex v, i.e., the number of edges with v an end point.



As all faces are triangles, we have 2E-n=3F,

Then E=3V-n-3.

Also 2E is the sum of the degrees of all vertices, and the degree of an inner vertices is at least 6, the sum of the degrees of the outer vertices is no more than 2E-6(V-n)=4n-6.

If n=3, 4n-6=6, the degree of each outer vertex must be two, which means there is no internal vertex, and E_3=1.

For n > 3, consider two cases:

(1) the degree of one outer vertex is 2, then we can remove that vertex and its edge and triangle, and down to the case of n-1. This case, the number of triangles is no more that 1+E_(n-1).

(2) Otherwise, there must be an outer vertex whose degree is 3, since the sum is 4n-6. We remove that vertex three edges, and two triangles; now an internal vertex becomes an outer vertex of degree at least 6-1=5. We keep this process, until case (1) occurs (it must occur...). We can do this process at most n/2 times, thus in this case, the number of triangles is no more than 2*(n/2)+1+E_{n-1}.

So E_n is no more than n(n+1)/2 (not very tight).