proof of Alon-Chung lemma
Let the vertices of be labeled by , and be the column vector defined by
for .
Let denote the adjacency matrix of . The number of edges in the subgraph
induced by equals , and we are going to show the following equivalent
inequality,
We label the eigenvalues of in decreasing order as
The largest eigenvalue is equal to the degree , and we let be the corresponding normalized eigenvector,
As is symmetric, there is a unitary matrix
that diagonalizes ,
The first column of is the column vector . We obtain
In the line above, the first term is
while the summation is equal to
Hence