  Exactly solvable models are essential in physics. For many-body spin-1/2
systems, an important class of such models consists of those that can be mapped
to free fermions hopping on a graph. We provide a complete characterization of
models which can be solved this way. Specifically, we reduce the problem of
recognizing such spin models to the graph-theoretic problem of recognizing line
graphs, which has been solved optimally. A corollary of our result is a
complete set of constant-sized commutation structures that constitute the
obstructions to a free-fermion solution. We find that symmetries are tightly
constrained in these models. Pauli symmetries correspond to either: (i) cycles
on the fermion hopping graph, (ii) the fermion parity operator, or (iii)
logically encoded qubits. Clifford symmetries within one of these symmetry
sectors, with three exceptions, must be symmetries of the free-fermion model
itself. We demonstrate how several exact free-fermion solutions from the
literature fit into our formalism and give an explicit example of a new model
previously unknown to be solvable by free fermions.
