$n^2-n+2$ plane divisions by $n$ circles

Question

Yesterday I learned that there can be at most $n^2-n+2$ plane divisions by $n$ circles.

Can someone help me understand why if I have $k$ circles on the plane, that divide it into $k^2-k+2$ parts, and draw another circle, then the maximum number of divisions it will add is $2k$? I can't seem to comprehend it.

I have seen proofs that just say:"It's obvious that this circle will intersect with each one of the others in at most $2$ points, so we get $2k$ new parts from $k$ circles". The fact that there are $2$ intersections for each circle don't make it obvious to me, that $2k$ new divisions will be added.

Answer 1

Consider a configuration with the maximum number of regions produced by $n$ circles. That is, every circle intersects each of the $(n-1)$ other circles in two points and no three circles meet at a single point. Now, consider the graph $G(V,E)$ where the vertex set $V$ is the set of the intersection points of this configuration, and the edge set $E$ is the set of circular arcs that connect two points in $V$ (without interruption by another intersection).

Now, we shall count $|V|$ and $|E|$. Note that each circle has $2(n-1)$ intersection points. There are $n$ circles, and each intersection point belongs to exactly $2$ circles. Therefore, the number of intersection points is $$|V|=\frac{1}{2}\,\big(2(n-1)\big)\,n=n(n-1)\,.$$ Now, each vertex in $V$ has degree $4$ (being the intersection of two circular arcs). Thus, by the Handshaking Lemma, we have $$\begin{align}|E|&=\frac{1}{2}\,\sum_{v\in V}\,\deg(v)=\frac{1}{2}\,\sum_{v\in V}\,4\\&=\frac{1}{2}\,\big(4|V|\big)=2|V|=2n(n-1)\,.\end{align}$$

To finish the proof, we need a little touch from Euler's formula for planar graphs: $$|V|-|E|+|F|=2\,,$$ where $F$ is the set of regions (i.e., plane divisions) formed by the planar graph. In this problem, $G$ is planar, so $F$ is well defined, and $|F|$ is the desired answer. We have $$\begin{align}|F|&=2+|E|-|V|\\&=2+\big(2n(n-1)\big)-\big(n(n-1)\big)\\&=n^2-n+2\,,\end{align}$$ which is exactly the answer to be proven.

Answer 2

Assume that you have $k$ circles which divide the plane into at most $k^2 - k + 2$ parts. Add a new circle. Consider intersections of this new circle with old circles. There are at most $2k$ such intersections. These points divide a new circle into at most $2k$ consecutive arcs. Each of these arcs divides at most $1$ old part into $2$ parts. Formally, you can also have more than one (say, $s$) arcs inside some old part. But these arcs are disjoint (except for endpoints) so the old part will be divided into at most $s + 1$ slices --- this means that there will be at most $s$ new parts. In total we can have at most $2k$ new parts. Thus after adding a new circle we can have at most $k^2 - k + 2 + 2k = (k + 1)^2 - (k + 1) + 2$ parts.