  The fourth listed author and Hans Parshall (\cite{IosevichParshall}) proved
that if $E \subset {\mathbb F}_q^d$, $d \ge 2$, and $G$ is a connected graph on
$k+1$ vertices such that the largest degree of any vertex is $m$, then if $|E|
\ge C q^{m+\frac{d-1}{2}}$, for any $t>0$, there exist $k+1$ points $x^1,
\dots, x^{k+1}$ in $E$ such that $||x^i-x^j||=t$ if the $i$'th vertex is
connected to the $j$'th vertex by an edge in $G$. In this paper, we give
several indications that the maximum degree is not always the right notion of
complexity and prove several concrete results to obtain better exponents than
the Iosevich-Parshall result affords. This can be viewed as a step towards
understanding the right notion of complexity for graph embeddings in subsets of
vector spaces over finite fields.
