  We consider the problem whether graph states can be ground states of local
interaction Hamiltonians. For Hamiltonians acting on n qubits that involve at
most two-body interactions, we show that no n-qubit graph state can be the
exact, non-degenerate ground state. We determine for any graph state the
minimal d such that it is the non-degenerate ground state of a d-body
interaction Hamiltonian, while we show for d'-body Hamiltonians H with d'<d
that the resulting ground state can only be close to the graph state at the
cost of H having a small energy gap relative to the total energy. When allowing
for ancilla particles, we show how to utilize a gadget construction introduced
in the context of the k-local Hamiltonian problem, to obtain n-qubit graph
states as non-degenerate (quasi-)ground states of a two-body Hamiltonian acting
on n'>n spins.
