  Frucht's theorem is the statement that "every group is the automorphism group
of a graph". This was shown over ZFC independently by Sabidussi and deGroot, by
induction using a well ordered generating set for the group. Sabidussi's proof
is easily modified to use induction on the rank of a generating set, and thus
holds over ZF.
  We show that Frucht's theorem is independent of ZFA set theory (ZF with
atoms), by showing it fails in several common permutation models. We also
present some permutation models where Frucht's theorem holds, even when AC
fails. As a corollary, we show that a stronger version of Frucht's theorem due
to Babai can fail without choice.

Logic