Exercise 4.7.2

For the cut in the middle, we have $P=1,2$ and $Q=3,4$. For $i$ in $P$ and $j$ not in $P$, we have

$\text{links}(P)=\sum <!--\; FUNCTION\; APPLICATION\; -->w_{\mathit{ij}}=w_{13}+w_{14}+w_{23}+w_{24}=4$, and the size of $P$ is

$\text{size}(P)=\sum <!--\; FUNCTION\; APPLICATION\; -->w_{\mathit{ij}}=w_{11}+w_{12}+w_{22}+w_{21}=4$

Similarly we have $\text{links}(Q)=4$, and $\text{size}(Q)=4$, so we compute the normalized cut weight:

$\text{Ncut}(P,Q)=\frac{\text{links}(P)}{\text{size}(P)}+\frac{\text{links}(Q)}{\text{size}(Q)}=\frac{4}{4}+\frac{4}{4}=2$

This is larger than the cut between 1 and 2 or the cut between 3 and 4, which has $\text{Ncut}(P,Q)=3+\frac{3}{6}>2$