(The lecture had material at the blackboard at this point
discussing... )

•Mathematical notion of __graph__** **= a set of vertices (*aka* nodes) and edges
connecting them

•A *k*-regular graph has exactly
*k* edges meeting at each vertex (i.e. valency=*k*)

•The adjacency matrix has
exactly *k* 1’s in each row and column

•Therefore the constant
vector whose entries are all equal to 1 is an eigenvector with eigenvalue *k
*

•If the graph is connected
all other eigenvalues are < *k*.

–There may be eigenvalues =
-*k
*

–All other eigenvalues are
strictly between –*k*
and *k
*

•A __expander sequence__ of graphs is one where
all other eigenvalues are bounded away from *–k* and *k *by an absolute, fixed amount.