# Cutting up a circle

December 28, 2009 Leave a comment

Suppose you have a circle. Choose a number of points on the edge of it, then join all these points to each other and see how many pieces the circle is split into. So for instance:

Obviously when you choose three points on the side you just have a triangle in a circle, which has 4 areas. When you choose two points on the side you just split the circle in half, giving you two areas.

It really looks like each time we add a point, we double the amount of areas we have. But in fact, this does not hold.

Now when we choose six points things are a little bit more complicated because depending on how you do it, you might get different numbers of areas. The picture below shows this:

To save you counting, the diagram on the left has 31 areas and the diagram on the right has 30 areas. By our pattern we would expect at least one of them to have 32, so that has gone out the window!

To get the most number of areas possible, we should never allow any three lines to meet at a single point (except for the at the points at the edge of the circle). Let’s carry on thinking about the maximum number. So the table goes:

So what about the 100th? We certainly can’t be bothered to draw a diagram for it. I guess the answer is to do some mathematics!

## Euler’s Formula

There is a well known theorem, first stated by Euler and first proven by Cauchy. It says that if you have a diagram (graph) that you can draw on paper without any lines crossing, then the number of **f**aces is equal to two more than the number of **e**dges joining the points minus the number of points (known as **v**ertices). That is:

For a proof and more information, look here.

## Applying Euler’s Formula

The problem is, our diagram usually can’t be drawn without any of lines crossing each other. In fact, the lines crossing each other to make new areas is exactly what this is about! But what we can do is add new vertices in so that it can. Thus, every time that two lines cross we add a point at their intersection. For instance:

Now to use the formula to find out how many faces we have, we must first find out how many vertices we have now, and how many edges we have now.

## Finding the number of vertices

We started with *n* vertices on the edge. How about the extra ones we added? Well, if you choose 4 different points on the edge then in the original version (before we added all the extra vertices), two of the lines connecting them would have to meet in a point. (Not any two of the lines, just a particular two. This is because you cannot draw the circle with 4 points without exactly one line crossing.) For instance:

Each crossing can also be related to two lines, and hence four points. Therefore there are exactly as many meeting points as there are ways to choose 4 points from *n.* That is, there are:

Adding in the *n* vertices we started with (the ones on the edge of the circle, remember?) we get:

## Finding the number of edges

We’re going to split the edges into three types. Those that connect vertices on the edge to other ones on the edge (directly), those which connect internal vertices to ones on the edge, and those which connect internal vertices together. That is:

Edges that go from one vertex on the circle to its immediate neighbour are definitely uncut. There are *n* of those. They are the blue lines on here:

And so straight away we have:

Now let us consider the number of edges that connect a vertex on the edge of the circle to one of the new ones on the inside.

Look at the picture below. Notice that one of the original lines is highlighted in red. It cuts through a number of lines and so and two ends of it are edges which connect the dots on the edge of the circles to one of the dots on the inside.

Now each of the original lines gives us two of these edges. So how many of the original lines are there? Well, there are as many as there are ways of choosing 2 points from *n*. That is,

However, this is wrong because it counts even the lines which were shown in blue above! These lines don’t cut anything and so should be excluded. Because there were *n* of them, that means that the actual number of edges that contribute is:

And so, as each line gives us two edges which connect points on the circle to the inside, the number of these are:

We now only have the final category of edges to go: Finding the number of edges which connect vertices on the inside to other vertices on the inside. The number of vertices on the inside of the circle was found earlier to be:

Now, each vertex has four edges connected to it, from the two lines which intercept it. So, think about the following number, which is four times the number of vertices inside the circle:

This number is counts four times the number of vertices inside the circle.

In the picture above, two vertices are considered. One of them, the green one, only connects to other internal vertices. The red one connects to three internal internal vertices and one on the circle. The green and the red also connect to each other and so you can see that *the internal edges will each be counted twice*. On the other hand, the edges which connect internal vertices to those on the circle are only counted once.

Therefore we have a formula:Now the term on the end was found above, and so we can substitute it in and rearrange to give:

Adding all these terms together, the number of edges is then:

So that is all the extra edges we have added. But in fact, we are missing some edges! Why? The circle itself! If we are considering the whole thing as a graph we should treat the circle itself as *n* edges. And so, in fact…

## All in all

All that is left to do is apply the formula!

Except you must remember that one of those areas is the area around the circle, and so the actual numbers of areas is:

(When *n* is 100 this is equal to 3 926 176, to answer the question at the start)

Here is the graph of this function: