# What is a non constructible graph?

I'm working through "Groups, Graphs and Trees" by John Meier.

In Chapter 5, he states that in a Cayley Graph, $$\Gamma$$ (or indeed any graph), the ball of radius n centred at the vertex v, $$\mathcal{B}(v,n)$$, is the subgraph formed as the union of all paths in $$\Gamma$$ of length $$\le n$$ that start at the vertex $$v$$.

It is then stated that a Cayley graph Γ is constructible if given $$n \in N$$ one can construct $$\mathcal{B}(e,n)$$ in a finite amount of time.

My question is what is an example of a non-constructible graph?

In particular, it is implied that there are finitely generated groups which have non-constructible Cayley graphs. I cannot comprehend what such a group looks like.

## 1 Answer

To construct the Cayley graph you need to be able to solve the word problem in the group, so any group with unsolvable word problem is an example.

In fact the converse is also true - if the group has solvable word problem then you can construct the Cayley graph.

• Would you be able to go into a specific example of such a group? I had seen the result you quoted in Meier but I am struggling to see what such groups are. Apr 22, 2022 at 14:16
• Such groups are complicated (and in some sense artificial), and constructed from Turing machines with unsolvable word problem using HNN extensions. If you really want to learn about them, I would recommend the final two chapters of Rotman's book "An Introduction to the Theory of Groups", Apr 22, 2022 at 16:01
• Okay, thanks. I think that intuitively had concluded these groups must be "artificial". I shall have a look at Rotman. Apr 22, 2022 at 17:10