Alon-Chung lemma

Let $G=(V,E)$ be a undirected graph of $n$ vertices such that the degree of each vertex is equal to $d$. Let $X$ be a subset of $V$. Then the number of edges in the subgraph induced by $X$ is at most

$$\frac{1}{2n}\left(d{|X|}^2+\lambda |X|(n-|X|)\right)$$

where $\lambda$ is the second largest eigenvalue of the adjacency matrix of $G$.

Reference: N. Alon and F. R. K. Chung, “Explicit construction of linear sizedtolerant networks,” Discrete Math., vol. 72, pp. 15-19, 1988.