When I was solving questions from a graph theory book by Bondy and Murty, I came across this problem:
( Note: $\Delta$ represents the maximum degree. )
Show that:
a) no eigenvalue of a graph G has absolute value greater than ∆,
b) if G is a connected graph and ∆ is an eigenvalue of G, then G is regular,
c) if G is a connected graph and −∆ is an eigenvalue of G, then G is both regular and bipartite.
I could prove a) and b). However my proof of b) was long and used a lot of calculation.
I hope b) and c) have nice proofs. Is there a short proof using some linear algebra and/or induction?
Thank you.
For (b), recall that $\lambda_{1}$ is the index of the graph. We take $\lambda_{1} = sup \{ x^{T} Ax : x \in \mathbb{R}^{n} \land ||x|| = 1 \}$, for $A$ as the adjacency matrix. When looking at $x = \frac{1}{\sqrt{n}} (1, ..., 1)$, we get $\lambda_{1} \geq \overline{d}$, the average degree. By Rayleigh's Principle, we get $\lambda_{1} = \overline{d}$ when $x$ is an eigenvector of $A$.
To get $\lambda_{1} = \Delta$, you will want to look at the fact that $G$ is k-regular if and only if $(1, ..., 1)$ is an eigenvector of $A$ with corresponding eigenvalue $k$.
For (c), do you have the theorem given that $G$ is bipartite if and only if its spectrum is symmetric with respect to the origin? It follows from this that if $G$ is connected, you only have to check that $\lambda_{1} = -\lambda_{n}$. If so, that will make proving (c) much easier. I would consider a proof by contrapositive here. What does it mean for $G$ not to be regular? The graph not being bipartite follows pretty quickly. Thus, your contraposition argument.
Edit: Expanding on (b) I was giving you a couple hints from which to work backwards, with $A\vec{1} = \Delta \vec{1}$. Hopefully that helps develop your intuition some, at least.
Take $det(A - \Delta I) = 0$, by definition of an eigenvalue. So what happens is that inserting $\Delta$ in the diagonal causes each row and column to add up to $0$. This creates a linear dependence. If we suppose $\Delta$ is an eigenvalue, but $G$ is not regular, we will get a contradiction, as $\det(A - \Delta I)$ will no longer be $0$. Play around with a couple examples. $C_{3}$ is a good example. Obviously it is $2$-regular. Try substituting a variable $\Delta$ in, instead of $2$ and crunching the determinant. Again, you will see that $\Delta = 2$ to satisfy the equality. Now what happens when you take a spanning tree of $C_{3}$ and suppose $\Delta = 2$ is an eigenvalue?
Looking at the eigenvectors, we note by definition that $Ax = \lambda x$, for $x$ an eigenvector. We get from this a bound that for any $x_{u}$, a component of $x$, that $\lambda x_{u} = \sum x_{v}$, where $x_{v}$ is adjacent to $x_{u}$. We can then bound $|\lambda| |x_{u}| \leq \sum |x_{v}| \leq \Delta |x_{u}|$, again where $x_{v}$ is adjacent to $x_{u}$. This bound occurs as we know that $|\lambda|$ is no bigger than $\Delta$. Now what happens if $G$ is $\Delta$-regular?