# Graph Theory - How many regions of an n-sided polygon with all chords added?

The question: Consider an $m-sided$ polygon with all of its chords added, and assume that no more than two of these chords cross at any one intersection point. Make the figure into a planar graph by regarding each junction as a vertex. Then use Euler's Theorem to find the number of regions into which the polygon is divided. (Note: the answers for $m=3,4,5,6$ are $1,4,11,25$, respectively.)

I've been thinking about this question for about an hour... I know that the number of regions in the polygon is just $f-1$. I don't know if I'm allowed to use recurrence relations to solve this problem, so for now I'm assuming I shouldn't. I know that the number of vertices is $m +$ the number of intersections of chords... I also think that each original vertex (i.e. on the polygon) has degree $m-1$ and each additional vertex has degree $4$..however I don't know how to count exactly how many edges there are since some vertices are incident to the same edge and so I'd overcount if I just summed up all the degrees.

I also think there are $m\frac{m-3}{2}$ chords, because each original vertex has degree $m-1$ and 2 of those are already taken up to make up the actual polygon, and you divide by 2 to not overcount since there are 2 vertices to every chord.

For example, for $m=5$, each original vertex has degree 4, 2 of those already account in the polygon, so each original vertex is incident to 2 chords, and we divide by 2 because 2 vertices are incident to the same chord.

Can anyone point me in the right direction? It'd be much appreciated.

Note that your $n$-gon has to be convex, or the solution will not work.
Consider the planar graph $G$ whose vertices are the (internal) intersections of the chords and the corners of the $n$-gon. $n(G)$ is the number of vertices of $G$.
Each 4 corners of the $n$-gon determine exactly one internal vertex, so we have $n+\binom n4$ vertices total. Each internal vertex has degree 4, each corner vertex has degree $n-1$, so with $e$ being the number of edges we get the degreesum $2e=n(n-1)+4\binom n4$, or $e=\binom n2+2\binom n4$
Finally Euler's formula gives us the number of regions (which is the number of faces minus the unbounded face), so we get $f-1=e-n(G)+1=\binom n2+2\binom n4-n-\binom n4+1= \binom n2+\binom n4-n+1$.
• And $\binom{n}2-(n-1)=\binom{n-1}2$, so the result can be simplified to $\binom{n}4+\binom{n-1}2$. – Brian M. Scott Apr 30 '15 at 21:02