So, I've been working on my graph theory homework, and I am stuck.
Here is the problem:
Consider an overlapping set of four circles $A, B, C, D$. One would like to position the circles so that every possible subset of the circles forms a region, e.g., $4$ regions each contained in just $1$ (different) circle, $6$ regions formed by the intersection of $2$ circles ($AB, AC, AD, BC, BD, CD$), $4$ regions formed by the intersection of $3$ of the four circles, and one region formed by the intersection of all $4$ circles. Prove that it is not possible to have such a set of $15$ bounded regions.
I don't even know where to start on this one... can someone help me out here? I'd be grateful.
Imagine you could have such an arrangement of circles. Let $G$ be the plane graph with vertices at each place two circles cross, and edges drawn as given by the circles. Note that $n=|V(G)|=\frac{4\cdot 6}2=12$ since each circle has six points of intersection, and each intersection involves two circles. Furthermore, $G$ is $4$-regular, so $m=\frac{4n}2=2n=24$. Finally $G$ has $r=16$ regions, the 15 bounded ones you mention, and the exterior unbounded region.
Then by the Euler identity, we have $n-m+r=2$, but $$n-m+r=12-24+16=4\neq 2.$$