Problem: Find the smallest rectangle on the integer grid that can be cut into pieces along grid lines, so that each piece has exactly five neighbors.
Pieces are neighbors, if their boundaries touch; touching in a corner doesn't count.
Here is a proof that $12$ is the smallest possible number of regions in any feasible solution.
Consider an arbitrary division of an arbitrary rectangle into $n$ regions, such that every region has exactly five neighboring regions. We translate this picture into a so-called planar graph: each of the $n$ regions then translates into a vertex/point, and there is a connecting edge between any two vertices/points that correspond to neighboring regions. The total number of edges is denoted $e$.
This can be seen by counting the touching vertex-edge pairs: every edge touches two vertices, and every vertex touches $5$ edges.
This fact can be found (for instance) on the wiki-page in the paragraph on maximal planar graphs. If follows from the Euler formula for planar graphs.
which implies $0\le n/2-6$ and hence $n\ge12$. Consequently, Lopsy's construction is best possible with respect to the number of used regions.
Not the answer you're looking for? Browse other questions tagged geometry dissection polyomino or ask your own question.