  We show that a quantum spin system has an exact description by
non-interacting fermions if its frustration graph is claw-free and contains a
simplicial clique. The frustration graph of a spin model captures the pairwise
anticommutation relations between Pauli terms of its Hamiltonian in a given
basis. This result captures a vast family of known free-fermion solutions. In
previous work, it was shown that a free-fermion solution exists if the
frustration graph is either a line graph, or (even-hole, claw)-free. The former
case generalizes the celebrated Jordan-Wigner transformation and includes the
exact solution to the Kitaev honeycomb model. The latter case generalizes a
non-local solution to the four-fermion model given by Fendley. Our
characterization unifies these two approaches, extending generalized
Jordan-Wigner solutions to the non-local setting and generalizing the
four-fermion solution to models of arbitrary spatial dimension. Our key
technical insight is the identification of a class of cycle symmetries for all
models with claw-free frustration graphs. We prove that these symmetries
commute, and this allows us to apply Fendley's solution method to each
symmetric subspace independently. Finally, we give a physical description of
the fermion modes in terms of operators generated by repeated commutation with
the Hamiltonian. This connects our framework to the developing body of work on
operator Krylov subspaces. Our results deepen the connection between many-body
physics and the mathematical theory of claw-free graphs.
