I've been trying to solve the following home task:

Choose $n$ points ($n\ge 2$) on the circle's circumference and connect them all with each other using chords. In result, the circle is divided into $R$ number of regions. Let $P$ be the number of intersection points and $S$ the number of (chord) segments.

Prove that $P-S+R=1$.

A hint is provided that it's not advised nor needed to try and find the exact counts for $P$, $S$ or $R$.

My first insight is that we can always create a regular polygon with $n$ sides if we put the points on circle equally spaced. So for example a pentagon has $P=5$, $S=20$ and $R=16$.

But here I'm stuck badly. Maybe we could apply Euler's polyhedron formula but I don't see how since it's for polyhedrons. The hint makes me think about an inductive approach. But if we start with $n$ points and add one more (that is, go from $n$-gon to ($n+1$)-gon), I don't see how we can make use of the induction assumption to proof the $(n+1)$ case.

Any insight is welcome!

  • 2
    $\begingroup$ You may use Euler's formula: Imagine that your drawing is placed on the northern half of a sphere and the southern half is an "empty" $n$-gon. $\endgroup$ – Christian Blatter May 2 '12 at 15:40

Here is an idea of a proof, similar to a proof for the Euler's formula:

Pick to adjacent points in the circumference, remove the chord corresponding to these points. Think about how R, S and P change, it is "obvious" that S decreases in 1, R decreases in 1 and P does not change.

This is the base for an inductive proof, you should work out what is the base case for the induction and you should write the "obvious" part above carefully.

EDIT: This does not work as pointed by randomguy in the comment below, but: You can cut the chords at every intersection point, this adds one point and one segment, so the invariant does not change. At the end you have a planar graph and you can apply the Euler's formula. But the comment of Christian Blatter gives a better idea.

  • $\begingroup$ Thank you. I do see the similarity with the proof of Euler's formula (in regards how the change in counts is observed), but fail to see how the results of removal of outer chords can be helpful to understand what goes on with the removal of points, diagonals or "inner" segments (the changes there seem to be much more complicated and unpredictable). $\endgroup$ – randomguy May 2 '12 at 18:11
  • $\begingroup$ To make it more clear what I meant to say: AFAIK Euler's formula is for planar graphs. Removal of the non-intersecting chords is trivial as you point out, but I fail to see how we can systematically remove an intersecting chord, since that has a variable effect on the $R$, $S$ and $P$. $\endgroup$ – randomguy May 2 '12 at 23:25
  • $\begingroup$ Ok, you have a point. I don't know how to fix the idea without copying the proof of the Euler's formula. $\endgroup$ – Quimey May 2 '12 at 23:52

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.