Show that max number of faces is $n^2/2 + n/2 + 1$ for an arrangement with $n(n-1)/2$ vertices and n^2 edges

Question

I cannot understand how to show that $$faces \leq n^2/2 + n/2 + 1$$ for an arrangement with $n(n-1)/2$ vertices and $n^2$ edges. By using Euler's formula I showed that $$faces = n^2 + n/2 + 2$$

I have no idea how to improve upon that. Does it mean that Euler's formula is not tight?

Answer 1

The Euler's formula for the polyhedron with $E$ edges, $V$ vertices and $F$ faces is: $$E=V+F-2 \Rightarrow F=E-V+2.$$ Plugging the given expressions: $$F=E-V+2=n^2-\frac{n(n-1)}{2}+2=\frac{n^2}{2}+\frac{n}{2}+2.$$ If any face of the polyhedron is removed, the equality changes to inequality: $$F<E-V+2.$$ For example, for the tetrahedron: $$F=E-V+2=6-4+2=4,$$ if one face is removed, then: $$F=3<6-4+2=4.$$