  For a finitely generated group $G$ the Nielsen graph $N_n(G)$, $n\geq
\operatorname{rank}(G)$, describes the action of the group
$\operatorname{Aut}F_n$ of automorphisms of the free group $F_n$ on generating
$n$-tuples of G by elementary Nielsen moves. The question of (non)amenability
of Nielsen graphs is of particular interest in relation with the open question
about Property $(T)$ for $\operatorname{Aut}F_n$, $n\geq 4$. We prove
nonamenability of Nielsen graphs $N_n(G)$ for all $n\ge
\max\{2,\operatorname{rank}(G)\}$ when $G$ is indicable, and for $n$ big enough
when $G$ is elementary amenable. We give an explicit description of $N_d(G)$
for relatively free (in some variety) groups of rank $d$ and discuss their
connectedness and nonamenability. Examples considered include free
polynilpotent groups and free Burnside groups.
