In this lecture, we generalized our setting to weighted graphs where is a positive weight function on edges. We also looked at the basic spectral theory of the *normalized Laplacian*, defined by

,

which operates on functions via

.

In particular, we associated with the normalized Rayleigh quotient,

,

and we showed that we can express the second-smallest eigenvalue as

.

We defined the *expansion* of a subset by

,

where is the characteristic function for .

Finally, we defined the *expansion of a graph* by

We then stated and (almost) proved the following discrete Cheeger inequality.

Theorem 1.For any weighted graph , we have,

where .

### Exercises (optional)

- Prove that for the normalized Laplacian, just as for the combinatorial Laplacian, the number of connected components in a graph G is precisely the multiplicity of the smallest eigenvalue.
- We saw the the right-hand inequality in Theorem 1 is asymptotically tight. Prove that the left-hand side is asymptotically tight for the complete graph on n nodes.