Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 4 / 16H (Graph Theory)

Let $A$ be the adjacency matrix of a graph and $Av=\lambda v$ with $v\ne 0$. Choose a vertex $i$ maximizing $|v_i|>0$. ThenDividing givesThis argument works even with a complex eigenvector; for a finite undirected graph the matrix is real symmetric and all eigenvalues are real.

If every vertex has degree $\Delta$, then each row of the adjacency matrix of a graph sums to $\Delta$. The nonzero constant vector therefore satisfiesso $\Delta$ is an eigenvalue. This uses the usual finite, nonempty graph convention.

For a $\Delta$-regular undirected graph, its Graph Laplacian is $L=\Delta I-A$, and for any complex vector $v$,If $Av=\Delta v$, the left side is zero, hence $v_i=v_j$ on every edge. In a connected graph all coordinates coincide. Thus the eigenspace is exactly the constant vectors, of dimension one. Since the adjacency matrix of a graph is symmetric and diagonalizable,

If a regular graph has $c>1$ connected components, the indicator vector of each component is a $\Delta$-eigenvector. They are linearly independent, and the Laplacian argument shows that every such eigenvector is constant on each component. Therefore its multiplicity is exactly $c$, in particular greater than one.

For the Petersen graph, each vertex has three neighbours, adjacent vertices have no common neighbour, and distinct nonadjacent vertices have exactly one common neighbour. The entries of $A^2$ count length-two walks, so diagonal entries are three, adjacent entries zero, and other off-diagonal entries one. HenceThe connected graph has the simple eigenvalue three with eigenvector $1$. On its orthogonal complement $J=0$, so the remaining eigenvalues satisfy ${\lambda }^2+\lambda -2=0$ and are one or minus two. If their multiplicities are $r,s$, then $r+s=9$ and $\mathrm{tr}A=3+r-2s=0$. Thus