Problem of the Month (April 2001)

This month we investigate adjacency graphs of sets of congruent polygons. Take a set of congruent polygons. Form a graph using the polygons as vertices, and draw an edge between two polygons if they share part of an edge. For example, the collection of squares below on the left has the adjacency graph below on the right.

Which graphs can be adjacency graphs? Can you find 4 congruent polygons that have K₄ (the complete graph on 4 vertices) as an adjacency graph? How about K₅ minus an edge? What are the simplest polygons (in terms of number of sides, or aspect ratio, or lack of small angles) that can realize a given adjacency graph? Can every tree be an adjacency graph?

For a real challenge, notice that the graph above is regular, meaning each square touches exactly three other squares. What are the smallest regular adjacency graphs? And what are the simplest polygons that create them?

ANSWERS

Joseph DeVincentis found chevrons with adjacency graphs K₄ and K₅ minus an edge. They are shown below.

Here are my polyomino solutions to these problems.

The first figure above was also found by John Hoffman who thinks that it cannot be done with a convex shape. Sasha Ravsky agrees. John Hoffman also asks whether every planar graph is realizable as an adjacency graph of a set of congruent polygons? He guesses no, but I guess yes. Can anyone find a counterexample?

Joseph DeVincentis found that a rectangle that can have an adjacency graph that is 4-regular. His arrangement is on the left. My arrangement is on the right.

In 2021, Isky Mathews proved that every tree is an adjacency graph.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 1/10/21.