Mackenzie Wheeler

An Introduction to Spectral Graph Theory

In this talk we give a brief introduction to the branch of combinatorics known as spectral graph theory. Spectral graph theory uses tools from linear algebra, such as the characteristic polynomials, eigenvalues, and eigenvectors of certain matrices, to prove properties of graphs. For a given graph $G$, the most common of the matrices studied in spectral graph theory are the adjacency matrix $A(G)$, and the Laplacian matrix, $L(G)$. We will define both $A(G)$ and $L(G)$ and present various graph theoretic properties associated with these matrices. In addition, we calculate the eigenvalues of $L(G)$ for several classes of graphs and conclude with Kirchoff’s theorem for enumerating labeled spanning trees of a given graph $G$.