  The number of homomorphisms from a finite graph $F$ to the complete graph
$K_n$ is the evaluation of the chromatic polynomial of $F$ at $n$. Suitably
scaled, this is the Tutte polynomial evaluation $T(F;1-n,0)$ and an invariant
of the cycle matroid of $F$. De la Harpe and Jaeger \cite{dlHJ95} asked more
generally when is it the case that a graph parameter obtained from counting
homomorphisms from $F$ to a fixed graph $G$ depends only on the cycle matroid
of $F$. They showed that this is true when $G$ has a generously transitive
automorphism group (examples include Cayley graphs on an abelian group, and
Kneser graphs).
  Using tools from multilinear algebra, we prove the converse statement, thus
characterizing finite graphs $G$ for which counting homomorphisms to $G$ yields
a matroid invariant. We also extend this result to finite weighted graphs $G$
(where to count homomorphisms from $F$ to $G$ includes such problems as
counting nowhere-zero flows of $F$ and evaluating the partition function of an
interaction model on $F$).
