question about the empire map

137 Views Asked by At

Given a planar map, an empire is a collection of disjoint regions. An empire with $m$ regions is called an $m$-pire. A planar map partitioned into empires is called an empire map.

Is it possible to construct an empire map in the plane with 11 mutually adjacent empires such that 9 of them are 2-pires and 2 are 1-pires?

1

There are 1 best solutions below

0
On

No, it is not possible. Indeed, assume that such a map exists. Let $G$ be its adjacency graph. Then $G$ should have at least ${11 \choose 2}=55$ edges to realize all adjacencies between different empires. On the other hand, $G$ is a planar graph on $9\cdot 2+2=20$ vertices and by a corollary from Euler’s formula $G$ can have at most $3\cdot 20-6=54<55$ edges.