# Find smallest rectangle divided into figures so each figure has 5 neighbours

The following 3x4 rectangle can be cut into pieces along grid lines, so that each piece has exactly three neighbors:

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.

• I'm guessing we should use at least 8 colours? Maybe 13, 18... – dmg Jan 24 '15 at 13:23
• @dmg You mean figures? Colours do not matter. Why do you think so? – Somnium Jan 24 '15 at 13:49
• You need at least 12 figures. Probably 12 figures gives the minimum, but it's annoying to optimize the rectangle size. – Lopsy Jan 24 '15 at 14:07
• I thought of this as a planar graph, where "points of touch" are edges, which gave 8 figures, but I made a typo in my formulae and it should be 12 as @Lopsy said. I think that this is a bit more constrained than a planar graph, but am not really sure – dmg Jan 24 '15 at 14:10
• Actually, I thought up this puzzle when was reading about planar graphs. – Somnium Jan 24 '15 at 14:13

How's this?

I got this by square-izing the icosahedron graph:

• I had solution of the same size and found with same manner. How about proof that this is minimal? – Somnium Jan 24 '15 at 14:24
• @Lopsy: Could you expand on how you "square-ized" the graph? The graph has 12 nodes, which I guess matches the 12 colours in your rectangle and I can see the "similarity". But I'm not sure about the procedure you've used for "square-izing". – BmyGuest Jan 24 '15 at 15:04
• No formal procedure, I just tried to squeeze it all into a square grid, starting from the center. Not sure how to approach a proof of minimality. – Lopsy Jan 24 '15 at 15:08
• Does anybody know the treewidth of the icosahedron graph? If the treewidth is $n$, then a rectangle containing it needs to have height and width at least $n$. I looks like it has treewidth 5 but I'm not sure. – Lopsy Jan 24 '15 at 15:24

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$.

We only need facts on $e$ and $n$

Fact 1: $~~~~2e=5n$

This can be seen by counting the touching vertex-edge pairs: every edge touches two vertices, and every vertex touches $5$ edges.

Fact 2: $~~~~e\le3n-6$

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.

Now by combining Facts 1 and 2, we get

$5n/2~=~e~\le~3n-6$,

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.