Let $G=(V,E)$ be a undirected graph with no self-loops. That is, for all $v,v'\in V$, $(v,v)\notin E$, and if $(v,v')\in E$ then also $(v',v)\in E$. Associate a qubit to each vertex in $V$. When necessary, the vertices will be indexed as $v_i$ with $i\in\{1,\dots, N\}$ where $|V|=N$. Let $I_N=I^{\otimes N}$ be the identity operator on all $N$ qubits, where $I$ is the identity operator on a single qubit. For some single qubit unitary $U$, write $U_{v_i}=I\otimes\cdots\otimes I\otimes U\otimes\cdots\otimes I$ to denote the operator on the $N$-qubit space which applies the single qubit unitary $U$ to the qubit associated to vertex $v_i$. Now, define the operators
\[
M_v=X_v\PROD{v':(v,v')\in E}{} Z_{v'}
\]
for $v\in V$, where $X_v$ and $Z_v$ are the single qubit $X$ and $Z$ operators acting on the qubit associated to vertex $v$.
For compatible operators $A$ and $B$, let $[A,B]=ABA^{-1}B^{-1}$. If $[A,B]=I$, then $A$ and $B$ \emph{commute}, and if $[A,B]=-I$ then $A$ and $B$ \emph{anticommute}. Now observe the following commutation relations:
\[
\begin{align*}
\text{for any} \ v_i,v_j\in V:& \ \ \ [I_N,X_{v_i}]=[I_N,Z_{v_i}]=[X_{v_i},X_{v_j}]=[Z_{v_i},Z_{v_j}]=I_N\\
\text{if} \ v_i\neq v_j:& \ \ \ [X_{v_i},Z_{v_j}]=I_N\\
\text{if} \ v_i=v_j:& \ \ \ [X_{v_i},Z_{v_j}] =-I_N.
\end{align*}
\]
These then imply the following commutation relations:
\[
\begin{align*}
\text{for any} \ v_i,v_j\in V:& \ \ \ \left[\PROD{v':(v_i,v')\in E}{} Z_{v'} \ , \ \PROD{v':(v_j,v')\in E}{} Z_{v'}\right]=I_N \\
\text{if} \ (v_i,v_j)\notin E:& \ \ \ \left[X_{v_i} \ , \ \PROD{v':(v_j,v')\in E}{} Z_{v'}\right]=I_N \\
\text{if} \ (v_i,v_j)\in E:& \ \ \ \left[X_{v_i} \ , \ \PROD{v':(v_j,v')\in E}{} Z_{v'}\right]=-I_N.
\end{align*}
\]
Trivially, for any graph $G$ and $v\in V$, the operator $M_v$ commutes with itself since $M_v^2=I_N$ as $M_v$ is only comprised of $X$ and $Z$ terms which satisfy $X^2=I$ and $Z^2=I$. Therefore, consider graphs $G$ with more than one vertex so that $|V|\geq 2$. For any two $M_{v_i}, M_{v_j}\in \{M_v\}_{v\in V}$ such that $v_i\neq v_j$, there are two cases two consider: either $(v_i,v_j)\notin E$ or $(v_i,v_j)\in E$.
Suppose first that $(v_i,v_j)\notin E$. Then $ Z_{v_j}$ does not appear in $M_{v_i}$, and likewise $Z_{v_i}$ does not appear in $M_{v_j}$. Then in the product $M_{v_i}M_{v_j}$, the pairs of operators that act on any particular qubit all commute. Therefore, $M_{v_i}M_{v_j}=M_{v_j}M_{v_i}$ so that $M_{v_i}$ and $M_{v_j}$ commute as well in this case.
Instead, suppose that $(v_i,v_j)\in E$. In this case, $ Z_{v_j}$ does appear in $M_{v_i}$, and likewise $Z_{v_i}$ appears in $M_{v_j}$. Then in the product $M_{v_i}M_{v_j}$ there are two pairs of operators that anticommute--namely, $X_{v_i}Z_{v_i}$ and $Z_{v_j}X_{v_j}$. Then since $X_{v_i}Z_{v_i}=-Z_{v_i}X_{v_i}$ and $Z_{v_j}X_{v_j}=-X_{v_j}Z_{v_j}$, the two resulting $-1$ factors will cancel. Hence, that $M_{v_i}M_{v_j}=M_{v_j}M_{v_i}$ implying that $M_{v_i}$ and $M_{v_j}$ commute. To see this more explicitly, consider the calculation shown below, which makes use of the nontrivial commutation relations given above:
\[
\begin{align*}
M_{v_i}M_{v_j}=&\left(X_{v_i}\PROD{v':(v_i,v')\in E}{} Z_{v'} \right)\left(X_{v_j}\PROD{v':(v_j,v')\in E}{} Z_{v'} \right)\\
&=(-1)X_{v_i}X_{v_j}\PROD{v':(v_i,v')\in E}{} Z_{v'}\PROD{v':(v_j,v')\in E}{} Z_{v'} \\
&=(-1)X_{v_j}X_{v_i}\PROD{v':(v_j,v')\in E}{} Z_{v'}\PROD{v':(v_i,v')\in E}{} Z_{v'} \\
&=(-1)(-1)X_{v_j}\PROD{v':(v_j,v')\in E}{} Z_{v'}X_{v_i}\PROD{v':(v_i,v')\in E}{} Z_{v'} \\
&=\left(X_{v_i}\PROD{v':(v_i,v')\in E}{} Z_{v'} \right)\left(X_{v_j}\PROD{v':(v_j,v')\in E}{} Z_{v'} \right)\\
&=M_{v_j}M_{v_i}.
\end{align*}
\]
It has now been shown that all operators in the set $\{M_v\}_{v\in V}$ commute with one another.
Since each operator $M_v$ contains the operator $X_v$, and any other $M_{v'}$ with $v\neq v'$ contains a different $X_{v'}$ operator, $M_v$ cannot be generated as a product of other $M_{v'}$ operators. Thus, the set $\{M_v\}_{v\in V}$ forms an independent set of commuting Pauli operators. Then the group $S_G:=<M_v>_{v\in V}$ generated by all $M_v$ forms a valid stabilizer group.
The stabilizer group $S_G=<M_v>_{v\in V}$ defines the code space
\[
T(S_G):=\{\ket{\Psi}\in(\mathbb{C}^2)^{\otimes n} \mid M_v\ket{\Psi}=\ket{\Psi}, \ \text{for all} \ v\in V \}.
\]
Furthermore, since are $|V|=N$ qubits and also $r=N$ independent generators, the number of encoded qubits expressed in $T(S_G)$ is given by $2^{N-r}=2^{0}=1$. Therefore, every graph $G$ can be associated to a unique (up to phase) state $\ket{\Psi_G}\in T(S_G)$ which encodes one logical qubit.
Suppose $G=C_n=(V,E)$ is the $n$-cycle graph with $n> 4$. Here, $V=\{v_1,v_2,\dots,v_n\}$ and $E=\{(v_a,v_b)\mid a\equiv b (mod \ n)\}$. Let $\ket{\Psi_{G}}\in T(S_G)$ be the associated graph state. Let $\mathcal{M}_{\bar{b}}\in S_G$, Then the projection onto $T(S_G)$ satisfies
\[
\ket{\Psi_G}\bra{\Psi_G}=\frac{1}{2^n}\SUM{U_a}{}U_a,
\]
since $T(S_G)$ is one dimensional. Denote by $Tr_{(i-1,i,i+1)}(\ket{\Psi_G}\bra{\Psi_G})$, the reduced density operator that results by tracing out all qubit registers except for those associated to neighboring registers $i-1, i$, and $i+1$ (where addition is taken $mod \ n$). Then
\[
Tr_{(i-1,i,i+1)}(\ket{\Psi_G}\bra{\Psi_G})=\frac{1}{2^n}\SUM{U_a}{}Tr_{(i-1,i,i+1)}(U_a).
\]
Hence, consider $Tr_{(i-1,i,i+1)}(U_a)$ for an arbitrary $U_a\in S_G$. Each $U_a$ is a product of some $M_v$ operators. If $U_a$ contains some $M_v$ which has nontrivial support on some vertex other than $v_{i-1},v_i$, or $v_{i+1}$, then $Tr_{(i-1,i,i+1)}(U_a)=0$, because the trace of any Pauli operator is $0$. Hence, the only nonzero contribution comes from $U_a=I$ and $U_a=M_{v_i}$ so that
\[\begin{align*}
Tr_{(i-1,i,i+1)}(\ket{\Psi_G}\bra{\Psi_G})=&\frac{1}{2^n}\SUM{U_a}{}Tr_{(i-1,i,i+1)}(U_a)\\
=&\frac{1}{2^n}\left(Tr_{(i-1,i,i+1)}(I)+Tr_{(i-1,i,i+1)}(M_{v_i})\right)\\
=&\frac{1}{2^{3}}\left(I+M_{v_i}\right) \\
=&\frac{1}{2^{3}}\left(I+X_{v_i}Z_{v_{i-1}}Z_{v_{i+1}}\right).
\end{align*}\]
Let $G=(V_G,E_G)$ and $G'=(M_{G'},E_{G'})$ be graphs and suppose $G'$ is obtained from $G$ by adding a vertex $v'$ which has no edges. Then $V_{G'}=V_G\cup\{v'\}$, and $E_{G'}=E_G$. Let $\ket{\Psi_G}\in T(S_G)$ and $\ket{\Psi_G'}\in T(S_{G'})$ be the associated graph states of $S_G$ and $S_{G'}$, respectively. In terms of $\ket{\Psi_G}$, the state $\ket{\Psi_{G'}}$ can be expressed as
\[
\ket{\Psi_{G'}}=\ket{\Psi_G}\otimes\ket{\varphi},
\]
where $\ket{\varphi}$ is a yet to be determined single qubit state.
In this case, the set of stabilizer generators for $G'$ is given by $\{M_v\}_{v\in V_G}\cup \{M_{v'}\}$, where $M_{v'}=X_{v'}$. All of the operators in $S_G$ act trivially on the state $\ket{\varphi}$ of $\ket{\Psi_{G'}}$, and the operator $M_{v'}$ acts trivially on all registers of the state $\ket{\Psi_{G'}}$ except for the qubit in the state $\ket{\varphi}$. However, since it must be the case that $M_v\ket{\Psi_{G'}}=\ket{\Psi_{G'}}$ for any $M_v\in S_{G'}$, then $\ket{\varphi}$ must be a $+1$ eigenstate of $M_{v'}=X_{v'}$. Therefore, $\ket{\varphi}=\ket{+}:=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$ as
\[
X\ket{+}=\frac{1}{\sqrt{2}}(X\ket{0}+X\ket{1})=\frac{1}{\sqrt{2}}(\ket{1}+\ket{0})=\ket{+},
\]
which shows that $\ket{+}$ is the unique $+1$ eigenstate of $X$. Hence, the associated graph state of $S_{G'}$ is given by
\[
\ket{\Psi_{G'}}=\ket{\Psi_G}\otimes\ket{+}.
\]
Now suppose $G'=(V_{G'},E_{G'})$ is obtained from $G=(V_{G},E_{G})$ by adding an edge $(v_1,v_2)$, where $(v_1,v_2)\notin E_{G}$, so that $E_{G'}=E_{G}\cup\{(v_1,v_2)\}$ and $V_{G'}=V_{G}$. Let $S_G=<M^G_v>_{v\in V_G}$ and $S_{G'}=<M^{G'}_v>_{v\in V_{G'}}$ be the stabilzer groups generated by the operators $M^G_v$ and $M^{G'}_v$, respectively. Then all of the operators in $S_{G'}$ and $ S_{G}$ are the same, except the operators $M^{G'}_{v_1},M^{G'}_{v_2}\in S_{G'}$ differ from those in $S_{G}$, by including additional $Z_{v_2}$ and $Z_{v_1}$ terms, respectively. That is,
\[
M^{G'}_{v_i}=
\left\{
\begin{array}{ll}
M^{G}_{v_i} \ \ \text{if} \ \ v_i \neq v_1, v_2 \\
\\
M^{G}_{v_i}Z_2\ \ \text{if} \ \ v_i=v_1\\
\\
M^{G}_{v_i}Z_1\ \ \text{if} \ \ v_i=v_2.\\
\end{array}
\right.
\]
Consider $\ket{\Psi_{G}}\in T(S_{G})$, and let $\ket{\Phi}=CZ_{z_1,z_2}\ket{\Psi_G}$, where $CZ_{z_1,z_2}$ is the two qubit phase gate applied to the qubits associated to vertices $v_1$ and $v_2$ given by
\[
CZ=\begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 &1 & 0 \\
0 & 0 & 0 & -1
\end{pmatrix}.
\]
Since $M^{G'}_{v_i}=M^{G}_{v_i}$ for $v_i\neq v_1, v_2$, and neither $X_{v_1}$ nor $X_{v_2}$ appear as factors in any of the operators $M^{G'}_{v_i}$ in this case, then each $M^{G'}_{v_i}$ commutes with $CZ_{z_1,z_2}$. Therefore,
\[
M^{G'}_{v_i}\ket{\Phi}=M^{G'}_{v_i}CZ_{z_1,z_2}\ket{\Psi_G}=CZ_{z_1,z_2}M^{G'}_{v_i}\ket{\Psi_G}=CZ_{z_1,z_2}\ket{\Psi_G}=\ket{\Phi},
\]
in the case where $v_i\neq v_1, v_2$.
For the other cases, first observe that $X_{v_1}Z_{v_2}CZ_{v_1,v_2}=CZ_{v_1,v_2}X_{v_1}$. Now suppose $v_i=v_1$, then
\[\begin{align*}
M^{G'}_{v_1}CZ_{z_1,z_2}=&M^{G}_{v_1}Z_{v_2}CZ_{z_1,z_2} \\
=&M^{G}_{v_1}X_{v_1}X_{v_1}Z_{v_2}CZ_{z_1,z_2} \\
=&M^{G}_{v_1}X_{v_1}CZ_{z_1,z_2}X_{v_1}\\
=& CZ_{z_1,z_2}M^{G}_{v_1}X_{v_1}X_{v_1} \\
=&CZ_{z_1,z_2}M^{G}_{v_1}.
\end{align*} \]
Hence, $M^{G'}_{v_1}\ket{\Phi}=M^{G'}_{v_1}CZ_{z_1,z_2}\ket{\Psi_G}=CZ_{z_1,z_2}M^{G}_{v_1}\ket{\Phi_G}=CZ_{z_1,z_2}\ket{\Psi_G}=\ket{\Phi}$. Therefore, for all $v_i\in V_{G'}$, it follows that $M^{G'}_{v_1}\ket{\Phi}=\ket{\Phi}$, implying that $\ket{\Phi}=CZ_{z_1,z_2}\ket{\Psi_G}\in T(S_{G'})$ is the encoded graph state of $S_{G'}$.
The consequences just shown can be applied to construct the graph state $\ket{\Psi_{C_4}}$ for the cycle graph $C_4$. In this approach, a Hadamard gate is applied to each of the four qubits (that all begin in the $\ket{0}$ state) which puts each qubit into the $\ket{+}$ state. Then a controlled phase $CZ_{v_i,v_j}$ for each pair of adjacent vertices is applied. The resulting state produced by this circuit will then be $\ket{\Psi_{C_4}}$.