  We present a general theory for the construction of witnesses that detect
genuine multipartite entanglement in graph states. First, we present explicit
witnesses for all graph states of up to six qubits which are better than all
criteria so far. Therefore, lower fidelities are required in experiments that
aim at the preparation of graph states. Building on these results, we develop
analytical methods to construct two different types of entanglement witnesses
for general graph states. For many classes of states, these operators exhibit
white noise tolerances that converge to one when increasing the number of
particles. We illustrate our approach for states such as the linear and the 2D
cluster state. Finally, we study an entanglement monotone motivated by our
approach for graph states.
