# Greatest number of parts that n circles can divide the plane

What is the greatest number of domains(or parts) that n circles could divide the plane?

From many small cases I get the feeling that intersecting circles would provide the greatest number of parts. Is this recursion right C(n+1) = 2C(n) using the previous statement. Since the new circle intersects all the circles and doubles the parts. Here C(n) is the number of parts for n circles.

How could I prove formally? If I could get an inequality that I will know for sure that I have got the greatest number of parts.

http://oeis.org/A014206 says draw n + 1 circles in the plane; then $a(n)=n^2+n+2$ gives the maximal number of regions into which the plane is divided. There are links and references there.

• the formula on the webpage is incorrect. It should be $a(n)=n^2-n+2$ – MaxW Sep 4 '16 at 7:09
• @Max, note that it's the formula for $n+1$ circles, not $n$ circles. – Gerry Myerson Sep 4 '16 at 13:03
• Sorry, many people seem to link to oeis website. Are there formal proofs there? I never seem to find any. The links lead to some pages, but there is never a rigorous proof. – Amrita Sep 4 '16 at 22:47
• That's right, @Amrita, there are hardly ever any proofs at oeis, that's not what that site is for. But there are often links to pages that do have proofs, and that's nearly the same thing. – Gerry Myerson Sep 4 '16 at 23:01
• I looked through most of the links, there seems to be no formal proof unfortunately – Amrita Sep 4 '16 at 23:08

The formula is'nt correct.

Looking at the problem as a planar garph: (you can think of every circle as 2 vertices we never intercect & 2 edges)

When adding a circle, we can intercect each previous circle in only 2 point, adding 2 vertices and 3 edges (one from the old circle). by Euler's formula it means we added one face.

so, in each step we add at most $n+1$ faces.(one of the new circle, $n$ from the n other circles).

Still, the question of the exact number is interesting.