From wikipedia we have : "The Bethe lattice where each node is joined to 2n others is essentially the Cayley graph of a free group on n generators." So solution for Your question, at least for a groups with finite number of generators, may be something likethat:
Graph V is a Cayley Graph for some group G if there exists graph B and equivalence relation of vertexes K such that:
- Graph B is Bethe lattice and has vertexes of order 2n ( every vertex is connected to 2n edges)
- V is isomorphic to B under K ( equivalence relation glues together vertexes.)
Relation to finite presentation of group and to free group seems to be natural here. The question is what if group has to have infinite number of generators. Of course I leave to You nontrivial part of proof ;-) which I do not know ;-) but I suppose relation between Bethe Latices and Cayley graphs seems to be central here because it is effective.
Note after Joel Comment:
Suppose we order edges which emanating from certain vertex. So we assign numbers 1, to first chosen edge, 2 to the second one and so on up to 2n for the last one. Then every edge emanating from certain vertex will have its number. As in Bethe lattice every vertex has the same structure of edges, we may propagate this way of ordering between all vertices, so every vertex has the same numbering. Then I believe that proper requirement we should set on our relation K is that it should state something only about finite ( or infinite in case of infinite generated group) sequence of edges, gluing only vertices for which sequence of edges is in relation. For example every vertexes connected by sequence (1,2,3) has to be glued ( what may describe situation that generators $g_1,g_2,g_3$ has to obey $g_1g_2g_3 = id$ relation ). Then this kind of relation is "global" in that meaning that it acts in the same way on every vertex. Probably it may be stated in more formal way...way:
1a. given is ordering system for edges emanating from every vertex
1b. relation K states only about vertexes connected by finite ( or infinite) sequences of edges ( which probably may be stated by requirement that relation K uses only edge sequences and not names of vertices)
Motivation: As regards to complexity: every finite presented ( or infinite presented I presume) group has infinite way of presentation, and also every group has relation K for which G=F/K where F is free group. For every group G You may set K to be equal the kernel of the group, that is a set of elements which are equal to identity. Of course they may be one or several optimal or simple ways of presenting of group by means of some kind of usability criteria, and usually K stated pure formally is far from being optimal. But it always existsAnd I agree, so probably use this property it is correct stated in very extravagant wayto state theorem You are asking for. I suppose that a question which require some "minimal relation K" for Bethe lattice here would be much harder to express. When there would be some kind of effective criteria on minimality, but probably they may be used in theory of presentation of groups, so they would be far from triviality, as this kind of problems, as far as I know, have not effective solution... But of course it would be much more interesting, whilst my way is probably near trivial...
