In quantum computing, graph states play a crucial role in quantum error correction and measurement-based quantum computing. Preparing these states efficiently on hardware with constrained connectivity is a fundamental challenge. In this work, we establish a universal framework for graph state preparation using only Controlled-Z (CZ) gates along the edges of a given hardware connectivity graph and local complementation operations. We prove that any graph state can be prepared using only these operations, providing a constructive transpilation method that transforms the input circuit into an equivalent one without increasing the number of entangling gates. Additionally, as our approach preserves entangling count and depth of the input circuit, we show that this framework also allows for optimal graph state preparation.