Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.