MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Frucht showed that every finite group is the automorphism group of a finite graph. The paper is here.
The argument basically is that a group is the automorphism group of its (colored) Cayley graph and that the colors of edge in the Cayley graph can be coded into an uncolored graph that has the same automorphism group.

This argument seems to carry over to the countably infinite case.
Does anybody know a reference for this?

In the uncountable, is it true that every group is the automorphism group of a graph? (Reference?) It seems like one has to code ordinals into rigid graphs in order to code the uncountably many colors of the Cayley graph.

share|cite|improve this question
up vote 15 down vote accepted

According to the wikipedia page, every group is indeed the automorphism group of some graph. This was proven independently in

de Groot, J. (1959), Groups represented by homeomorphism groups, Mathematische Annalen 138


Sabidussi, Gert (1960), Graphs with given infinite group, Monatshefte für Mathematik 64: 64–67.

share|cite|improve this answer
Thanks. I somehow missed that wikipedia page. I only found the one with the Frucht graph and related paper. – Stefan Geschke Sep 1 '10 at 8:37
From de Groot's paper you can see that this argument you described goes pretty far, for graphs, topological spaces etc. Coding arbitrary number of colors is done through some rigid spaces with no automorphisms. – Gjergji Zaimi Sep 1 '10 at 8:53
Yes, Stefan certainly had the right idea in mind. I'll just remark that Sabidussi's paper meets my requirements for recreational math reading; it's only three pages long. – Tony Huynh Sep 1 '10 at 9:10

In the topological setting or if you want to relate the size of the graph to the size of the group, there are two relevant results:

(1) Any closed subgroup of $S_\infty$, i.e., of the group of all (not just finitary) permutations of $\mathbb N$, is topologically isomorphic to the automorphism group of a countable graph.

(2) The abstract group of increasing homeomorphisms of $\mathbb R$, ${\rm Homeo}_+(\mathbb R)$, has no non-trivial actions on a set of size $<2^{\aleph_0}$. So in particular, it cannot be represented as the automorphism group of a graph with less than continuum many vertices.

share|cite|improve this answer
Hi Christian! Nice to see you here. – Andrés E. Caicedo Sep 1 '10 at 17:04
Hi Christian! Nice to see you! I fixed a small typo in your post. – François G. Dorais Sep 1 '10 at 17:47
This is interesting, thank you. – Stefan Geschke Sep 2 '10 at 8:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.