  We address the question of quantifying entanglement in pure graph states.
Evaluation of multipartite entanglement measures is extremely hard for most
pure quantum states. In this paper we demonstrate how solving one problem in
graph theory, namely the identification of maximum independent set, allows us
to evaluate three multipartite entanglement measures for pure graph states. We
construct the minimal linear decomposition into product states for a large
group of pure graph states, allowing us to evaluate the Schmidt measure.
Furthermore we show that computation of distance-like measures such as relative
entropy of entanglement and geometric measure becomes tractable for these
states by explicit construction of closest separable and closest product states
respectively. We show how these separable states can be described using
stabiliser formalism as well as PEPs-like construction. Finally we discuss the
way in which introducing noise to the system can optimally destroy
entanglement.
