# Entanglement entropy for graph states defined on a tree graph

Consider a $$k-\text{ary}$$ tree $$T$$, for a constant $$k$$. Consider the corresponding graph state $$|\mathsf{G}_T \rangle$$ that is defined on $$T$$.

Is it true that $$|\mathsf{G}_T \rangle$$ saturates the area law for entanglement entropy, across any bipartition? It is easy to prove that the entanglement entropy for $$|\mathsf{G}_T \rangle$$, across any bipartition, can be upper bounded by an area law. Does it saturate the bound too?

Think about the process of building a graph state: create qubits in the $$|+\rangle$$ state and apply controlled-phase gates along all the edges.
Now take a bipartition. You can apply any unitary that you want on either side of the partition, so perform controlled-phase gates along all edges not crossing the partition. Let's say the connected qubits on either side of the partition are in sets $$S_1$$ and $$S_2$$, where $$S_1$$ is smaller (or the same size) as $$S_2$$. You are only left with entangled states across the partition, and they require a number of Bell pairs to build that is equal to $$|S_1|$$.
To make this explicit, let $$x\in\{0,1\}^{|S_1|}$$ and let's call $$N(x)\in\{0,1\}^{|S_2|}$$ the neighbourhood of $$x$$, by which I strictly mean that bit $$i$$ of $$N(x)$$ is the parity of neighbours $$j$$ of $$i$$ for which $$x_j=1$$. Now I can write the graph state (after my unitaries) as $$\sum_{x\in\{0,1\}^{|S_1|}}|x\rangle\otimes Z_{N(x)}|+\rangle^{\otimes|S_2|}.$$ Now since all the $$Z_{N(x)}|+\rangle^{\otimes|S_2|}$$ are orthogonal for distinct $$x$$ (I believe this follows from the fact that you have a tree, and hence no loops), we can see that the way I've written the graph state is a Schmidt decomposition for a maximally entangled state of $$|S_1|$$ qubits.