Conway's Tiling Groups

John Conway discovered a technique using infinite, finitely presented groups that in a number of interesting cases resolves the question of whether a region in the plane can be tessellated by given tiles. The idea is that the tiles can be interpreted as describing relators in a group, in such a way that the plane region can be tiled, only if the group element which describes the boundary of the region is the trivial element 1. A convenient way to describe the construction is by means of the Cayley graph or graph of a group. If G is a group, then its graph F(G) with respect to generators g1, g2 . . ., gn is a directed graph whose vertices are the elements of the group. For each vertex v E F(G), there will be n outgoing edges, labeled by the generators, and n incoming edges: the edge labeled gi connects v to vgi. It is convenient to make a slight modification of this picture when a generator gi has order 2. In that case, instead of drawing an arrow from v to vgi and another arrow from vgi back to v, we draw a single undirected edge labeled gi. Thus, in a drawing of the graph of a group, if there are any undirected edges, it is understood that the corresponding generator has order 2. The graph of a group is automatically homogeneous: for every element g E G, the transformation v -4 gv is an automorphism of the graph. Every automorphism of the labeled graph has this form. This property characterizes graphs of groups: a graph whose edges are labeled by a finite set F such that there is exactly one incoming and one outgoing edge with each label at each vertex is the graph of a group if and only if it admits an automorphism taking any vertex to any other. Whenever R is a relator for the group, that is, a word in the generators which represents 1, then if you start from v EF rand trace out R, you get back to v again. If G has presentation