# Normalized Cuts and Spectra

I'm looking for a fleshed out proof of the following theorem.

Theorem: Let $G=(V,\mathbf{W})$ be an undirected, edge-weighted graph with normalized Laplacian $\mathbf{L}_N$. Furthermore, let $0=\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_{n-1}\leq 2$ be the eigenvalues of $\mathbf{L}_N$. Choosing some $k$ such that $k<n$ and $\lambda_{k-1}<\lambda_k$, we have that,

$\text{Ncut}(A_1,...,A_k) \geq \sum\limits_{i=1}^{k-1}\lambda_i$

where $\text{Ncut}(A_1,...,A_k) := \sum\limits_{i=1}^k\frac{W(A_i,\overline{A_i})}{\text{vol}(A_i)}$. Any help is appreciated, thanks!

-
If I understand correctly, $\operatorname{vol}(A_i) = \sum_{v \in A_i} \deg(v)$. However, what is $W(A_i, \overline{A_i})$? –  Andrew Uzzell Dec 10 '12 at 9:28
Also, how are the sets $A_1$, $\ldots\,$, $A_k$ defined? –  Andrew Uzzell Dec 13 '12 at 14:49
add comment