2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ And $\binom{n}2-(n-1)=\binom{n-1}2$, so the result can be simplified to $\binom{n}4+\binom{n-1}2$. $\endgroup$ – Brian M. Scott Apr 30 '15 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.