Geographic Graph Theory
by agbdmrbirdyface, Aug 10, 2016, 7:15 PM
This is a simple graph theory problem... with a geo problem thrown in for good measure.
Solution:
Classic Problem wrote:
Suppose you are to tile the Earth with square tiles, with the following rules:
Touching tiles must match along their edges, and they should have roughly square corners. Hence, if two tiles touch, they must touch at a corner or along an entire edge of each tile. Wherever tiles meet at a corner, exactly 4 tiles must meet at that corner. The tiles don't have to be exactly square, and can be of different sizes, but each tile should have side length at least an inch and at most one mile.
Show it is either possible or impossible to find such a tiling. If it is impossible, show why it is, and if it is possible, find such a configuration.
Touching tiles must match along their edges, and they should have roughly square corners. Hence, if two tiles touch, they must touch at a corner or along an entire edge of each tile. Wherever tiles meet at a corner, exactly 4 tiles must meet at that corner. The tiles don't have to be exactly square, and can be of different sizes, but each tile should have side length at least an inch and at most one mile.
Show it is either possible or impossible to find such a tiling. If it is impossible, show why it is, and if it is possible, find such a configuration.
Solution:
We claim that this tiling of the Earth is impossible.
This is basically asking whether or not there exists a planar graph with all faces having size
and each vertex having degree
on a sphere. This is also equivalent to having the same conditions on a planar graph on a regular plane since it is possible to project any graph on a sphere onto a regular plane.
Assume for the sake of contradiction that this graph is planar. If it satisfies the conditions for a planar graph on a plane, then it should satisfy Euler's Formula, where:

Suppose we use
tiles to tile Earth. Then
for obvious reasons.
To count the number of edges with this configuration with
faces, we realize that each face has
edges, for a total of
edges. However, we have over counted by a factor of two, since each edge borders two faces, for an actual value of
edges. The number of vertices is also easily counted, with
vertices over all the faces, but then we overcount by a factor of 4 since 4 faces share each vertex, for
vertices.
We may plug our values of
,
, and
into Euler's Formula:


This is clearly false, so we have a contradiction. Hence no planar graph of this sort exists, and thus we cannot tile the Earth with square tiles.
This is basically asking whether or not there exists a planar graph with all faces having size


Assume for the sake of contradiction that this graph is planar. If it satisfies the conditions for a planar graph on a plane, then it should satisfy Euler's Formula, where:

Suppose we use


To count the number of edges with this configuration with






We may plug our values of





This is clearly false, so we have a contradiction. Hence no planar graph of this sort exists, and thus we cannot tile the Earth with square tiles.