Can we mesh a rectangle using only heptagons?

Question

I know that according to Euler's formula in graph theory the average number of edges or vertices in a planar connected graph cannot exceed six. So it seems according to Euler's formula its not possible mesh any plane using only heptagons (or say 80-90% heptagons). I am trying to write a code in MATLAB to mesh a rectangular domain using heptagons but don't know if its possible or not. Can someone tell me if its possible and if yes, then why?

Answer 1

It is perfectly possible to tile a finite region of the plane using heptagons, it is just that they won't all have the same size and shape. The more tiles you use, the more they get distorted towards the edge of your region.

For example, take a look at this representation of the heptagonal tiling of the hyperbolic plane:

(Picture was taken from this wiki page)

In a so-called hyperbolic plane, this would be a regular tiling. Loosely speaking, a hyperbolic plane gives you more than 360 degrees of angle space at every point, allowing you to fit three regular heptagons together. In the normal Euclidean plane this is not the case, which is why in this flat-plane picture the heptagons are distorted. They get smaller the further from the centre in order to fit them all into the flat plane while still keeping them essentially the same shape.

If you cut out a rectangle from that picture, you have a tiling of that rectangle with heptagons (except for the tiles at the edges, but that is unavoidable).

You don't have to make the outer heptagons smaller in area, but you will find that they have to be narrower. If you start with a central regular heptagon, and add a layer of heptagons around it, then surround that by another layer, and so on, then with each layer you get more and more tiles than should fit in the flat plane. The only way to have each tile have the same area as a tile in the previous layer is to make each successive layer thicker by stretching the heptagons in the radial direction.

So you can tile a region of the plane with heptagons, but the more tiles you use, the worse it gets around the boundary. Essentially Euler's formula gets imbalanced, and this gets compensated for at the boundary by having more and more vertices that don't have neighbouring tiles (yet).

EDIT:

I'll use "unmatched vertex" to mean a vertex that is adjacent to only one tile, so has only two edges coming from it. A finished tiling has no unmatched vertices. An unmatched vertex needs (at least) two more tiles placed next to it, or equivalently needs (at least) one more edge added to it.

In a patch of heptagons, the ones on the boundary generally have 3 or 4 unmatched vertices. So there are 1 or 2 edges between two unmatched vertices on each boundary heptagon. If you add a layer of pentagons around them, each pentagon on such an edge will introduce another unmatched vertex that you have to deal with.

Therefore you will either need further partial layers pentagons (this makes some of the pentagons internal to the tiling, which may be undesirable), or you will need some quadrilaterals as well.

A layer of pentagons and quadrilaterals is sufficient. Simply add edges from the unmatched vertices of the patch of heptagons to the outer rectangle.

EDIT 2:

Here is a table showing the number for each extra layer of heptagons placed around a central heptagon.

       Heptagons                Fraction
       3 unm   2 unm   Total    Quadr     Penta     Hepta
   0       -       -       1   
   1       7       0       8    0.875     0         0.125
   2      14       7      29    0.482759  0.241379  0.275862
   3      35      21      85    0.411765  0.247059  0.341176
   4      91      56     232    0.392241  0.241379  0.366379
   5     238     147     617    0.385737  0.238250  0.376013
   6     623     385    1625    0.383385  0.236923  0.379692
   7    1631    1008    4264    0.382505  0.236398  0.381098
   8    4270    2639   11173    0.382171  0.236194  0.381634
   9   11179    6909   29261    0.382044  0.236116  0.381839
  10   29267   18088   76616    0.381996  0.236086  0.381918
                                  ...       ...       ...
                                0.381966  0.236068  0.381966

The first two columns show the two types of heptagons in the outer layer, those with 3 and those with 2 unmatched vertices. The third column is the total number of heptagons from all layers so far.

Each row is easily calculated from the previous row. If the $n$th row is $a_n$, $b_n$, $c_n$, then we have $a_n=2a_{n-1}+b_{n-1}$, and $b_n=a_{n-1}+b_{n-1}$. We also obviously have $c_n=c_{n-1} + a_n+b_n$.

If you have your rectangle cut through all the heptagons in the outer layer, then the heptagons with 3 unmatched vertices become quadrilaterals, and those with two become pentagons. The fraction of quadrilaterals is therefore $a_n/c_n$, the fraction of pentagons $b_n/c_n$, leaving $1-a_n/c_n-b_n/c_n$ for the fraction of heptagons.

The limit for the fraction of heptagons is about $38.1966\%$. You could solve the recurrence relations to prove this is $(3-\sqrt{5})/2$.

Note that if you arrange the heptagons differently, then it will be less compact and expose more vertices on the boundary, making the fraction of heptagons smaller.

Even if you let the heptagons share an edge with the rectangle boundary, and fill in the remaining boundary gaps with triangles and pentagons, I think you still won't get more than about 50% heptagons in your mesh. Reaching 80-90% is not possible.