Brief Review
of Graph Theory

•__Definitions:__
A graph G is a collection
of vertices V,
and (undirected) edges E connecting the vertices.

•A k-regular graph has exactly k edges meeting at
each vertex.

•Adjacency
operator A on L2(V) averages
the function
over its neighbors

A:
f(x) ! åy~x f(y)

•The constant
functions on V are
eigenfunctions with the *trivial* *eigenvalue* l = k.