Into how many regions do the sides and diagonals of a convex $n$-gon divide the plane, if no three meet at an interior point?

Question

Suppose that the complete graph $K_n$ with $n$ vertices is drawn in the plane so that the vertices of $K_n$ form a convex $n$-gon, each edge is a straight line, and no three edges cross at a point. Let $f(n)$ be the number of regions that this drawing divides the plane into. For example, the following picture shows that $f(4)=5,$ as the drawing divides the plane into five regions

Find, with proof, a closed-form formula for $f(n)$.

Euler's formula is most likely useful in this question if I could guess, but it only applies to planar graphs: $$\text{#of vertices}+\text{#of faces}=\text{#of edges}+2$$

Answer 1

Here's an explanation of what I mean: Consider the figure before the red diagonals have been added. The interior of the polygon has been divided into $5$ regions: $4$ in the interior of the quadrilateral $ABCD$ and the triangle $ADE$. How many regions are added when we draw diagonal EB? The diagonal is divided into $3$ segments by its intersections with the black diagonals. Each of these segments divides a pre-existing region in two, so it adds $3$ regions. The same can be said for diagonal EC, so $6$ regions are added, making $11$ regions. Then the unbounded region makes $12$.

Now, how can we know how into many segments diagonal EB is divided without drawing a picture? Well, it's one more than the number of diagonals it intersects? $EB$ intersects two diagonals because there is one vertex ($A$) on one side of it, and two vertices ($C,D$) on the other side. Each vertex on one side is joined by a diagonal to each vertex on the other side.

Now, try to generalize this argument.

Answer 2

If we can tell how many vertices and edges are created by the addition of one vertex to the polygon as a planer graph, we can use Euler's formula to derive the solution by induction.

any n-vertex convex polygon can be transformed to a (n-1)-vertex one simply by removing one vertex and all of it's corresponding edges. assuming we know the amount of faces $f(n-1)$, let's count how many more faces are added by bringing back our deleted vertex.

by redrawing our vertex and connecting it to its two non-diagonal neighbors, we added one vertex and two edges to the graph, by Euler's formula we added one face (trivial by common sense). now let's count the diagonals. each diagonal between our new vertex and some other vertex divides the rest of the vertices into two sets. since our polygon is convex, all of the edges with one end in each set are the only edges intersecting our diagonal. we can thus count the amount of intersections simply as the multiplication of the length of the two sets. this would be the amount of new vertices created by each diagonal, and since each of these vertices splits an already placed edge to two, it is also the amount of new edges added not accounting for our new diagonal. these two cancel each other according to Euler's formula, so the amount of faces added by each diagonal is simply the amount of edges our diagonal was divided to by the already placed diagonals, which is the amount of its intersections plus 1.

all that is left is to sum this value for all of the diagonals: $$\sum_{i=1}^{n-3}i * (n-i-2) + 1$$

so our final solution is: $$f(n) = f(n-1) + 1 + (\sum_{i=1}^{n-3}i * (n-i-2) + 1)$$ (you might be able to simplify it with some algebra)