**Abstract**
We present an elegant way of representing closest separable states in terms of relative entropy of entanglement to graph states using stabilizer formalism. This method allows us to study multipartite entanglement using graph theoretic language. We demonstrate that searching the Hilbert space for separable state that minimizes relative entropy is equivalent to searching for the maximum independent set of a graph state in a particular equivalence class generated by local Clifford transformations. Our approach reproduces known entanglement scaling for 2-colorable graph states such as cluster states and achieves the lower bounds previously obtained for non-2-colorable graph states such as a ring with odd number of qubits. Furthermore we demonstrate how our approach can be used to find the Schmidt representation of these pure graph states pointing to a previously unrecognized relationship between relative entropy of entanglement and Schmidt measure.