  In this paper, we discuss the entanglement properties of graph-diagonal
states, with particular emphasis on calculating the threshold for the
transition between the presence and absence of entanglement (i.e. the
separability point). Special consideration is made of the thermal states of
trees, including the linear cluster state. We characterise the type of
entanglement present, and describe the optimal entanglement witnesses and their
implementation on a quantum computer, up to an additive approximation. In the
case of general graphs, we invoke a relation with the partition function of the
classical Ising model, thereby intimating a connection to computational
complexity theoretic tasks. Finally, we show that the entanglement is robust to
some classes of local perturbations.
