Suppose we are given a simple graph $G$ (i.e. without loops and multiple edges) on $n$ vertices that is $d$-regular, in the sense that every vertex has degree $d$. Then, if $\lambda_{1}\leq\dots\leq\lambda n$ are its eigenvalues (i.e. the eigenvalues of its adjacency matrix A:=A(G)) then, we can say the following:
\begin{equation} \label{aa} \tag{(1)}
-d\leq \lambda_{1}\leq\dots\leq\lambda_{n}=d
\end{equation}
where the equality $\lambda_{1}=-d$ holds if and only if $G$ has a connected component which is bipartite. It can also be proved that the multiplicity of the eigenvalue $d$ gives us the number of connected components of $G$. We can prove \ref{aa} using the Rayleigh quotient $R_{A}(x)=\frac{x^{T}Ax}{x^{T}x}$ for non-zero vectors $x\in \mathbb{R}^{V}$ as follows:
It is known in linear algebra that
\begin{equation}
\lambda_{n}=\max_{x\neq 0}R_{A}(x) \ \ \ \ \ \ \ \text{and} \ \ \ \ \ \ \
\lambda_{1}=\max_{x\neq 0}R_{A}(x).
\end{equation}
To prove that $-d\leq \lambda_{1}\leq\lambda_{n}\leq d$ we compute the Rayleigh quotient
$R_{A}(\mathbf{1})$, for the unit vector $\mathbf{1}=(1)_{v\in V}$.
\begin{equation} \label{bb}\tag{(2)}
R_{A}(\mathbf{1})=\frac{\mathbf{1}^{T}A\mathbf{1}}{\mathbf{1}^{T}\mathbf{1}}=\frac{\sum_{u,v\in V}A_{u,v}}{n}=
\frac{\sum_{u\sim v}2A_{u,v}}{n}=\frac{\sum_{u\sim v}2}{n}=
\frac{2m}{n}=\frac{dn}{n}=d,
\end{equation}
where in the last but one equality we use the hand-shaking lemma. To prove now the equality $\lambda_{n}=d$ it is enough to prove that for all $x\in \Bbb{R}^{V}\setminus\{0\}$ it holds that $R_{A}(x)\leq d$, which is equivalent to $x^{T}Ax\leq dx^{T}x$. This is indeed the case as we have that
\begin{align}
x^{T}Ax\leq dx^{T}x &\iff \sum_{u,v\in V}A_{u,v}x_{u}x_{v}\leq\sum_{u\in V}dx_{u}^2 \\
&\iff
\sum_{u\sim v}2x_{u}x_{v}\leq \sum_{u\sim v} x_{u}^{2}+x_{v}^{2} \\
&\iff 0\leq \sum_{u\sim v} (x_{u}-x_{v})^{2},
\end{align}
where we have used the counting argument that for a graph $G$ it holds that
$\sum_{u\in V}\deg(u)x_{u}^{2}=\sum_{u\sim v}x_{u}^{2}+x_{v}^{2}$.
My Question is the following: What can I say about the spectrum of a $d$-regular multigraph, i.e. a graph in which we allow loops and multiple edges?
I have managed to prove that if $G$ is a $d$-regular multigraph without loops then we have that the spectrum of $G$ lies in $[-d,d]$. For this I use a fact from linear algebra that a strictly diagonally dominant square $n\times n$ matrix $M$ is invertible, where by strictly diagonally dominant I mean that for every $1\leq i\leq n$ it holds that $|M_{i,i}|>\sum_{j\neq i}|M_{i,j}|$. So, I want to prove that if $|\lambda|>d$ then
$\lambda$ is not an eigenvalue of $A=A(G)$, which means that $\lambda I-A$ is invertible.
But the diagonal values of $\lambda I-A$ are $\lambda-A_{v,v}=\lambda$ since $G$ is assumed loop-less and we also have that $|\lambda|>d=\sum_{u\neq v}A_{u,v}$. Hence, $\lambda I-A$
is strictly diagonally dominant; hence invertible!
What about a multigraph with loops? I cannot find a counterexample to that bound!
Also, it is obvious that $d$ is always an eigenvalue of such a graph as $\bf{1}$ is an eigenvector of $A$ corresponding to that eigenvalue, i.e. $A\mathbf{1}=d\mathbf{1}$.
However, the spectrum of the 2-regular multigraph (the loop contributes 2 to the degree)
is $-2\leq -1\leq -1\leq 2$, but this is not a connected graph neither it is bipartite.
Thus, the characterization given by the eigenvalues on a simple graph does not hold in general. Does it hold in a more restricted class of multi-graphs? Can I modify a multi-graph to a simple graph in order to study it that way?
My question arises from the fact that I have seen many authors using the properties that the graph spectrum gives to the respective graph even if they speak about multigraphs!
Correction: The computation of the graph above is false. I cannot find a counterexample to the proposition.
Best Answer
The statement
is false. Everything you've said about eigenvalues of a simple graph continues to hold for multigraphs, even with loops.
In the example multigraph, the adjacency matrix must be taken to be $$\begin{bmatrix}0 & 2 & 0 \\ 2 & 0 & 0 \\ 0 & 0 & 2\end{bmatrix}.$$ Though in general, there is some disagreement about how to record loops in an adjacency matrix, there is no alternative here if we want the matrix to "know" that the loop contributes $2$ to the degree.
The eigenvalues of this matrix are $-2, 2, 2$. This accurately reports that:
Here is a proof of both claims that generalizes to multigraphs.
In one direction, given a connected component, the indicator vector of that component is an eigenvector of $d$. If the component is bipartite with bipartition $X \cup Y$, the vector which is $1$ on $X$, $-1$ on $Y$, and $0$ outside that component is an eigenvector of $-d$. Now we have to argue that these vectors span the eigenspaces of $d$ and $-d$ respectively.
Suppose $\mathbf x$ is an eigenvector of $d$: $A\mathbf x = d\mathbf x$. Let $i$ be any vertex so that $x_i$ is the largest value of $\mathbf x$ on $i$'s component. Then on the one hand, $(A\mathbf x)_i = d \cdot x_i$, because eigenvector.
On the other hand, $(A\mathbf x)_i$ is the sum of the values of $\mathbf x$ on $i$'s neighbors. This counts them with multiplicity if there are parallel edges, and may count $i$ several times if there are loops. But in any case, it's the sum of $d$ values that are all at most $x_i$. So it can only reach the value $d \cdot x_i$ that it should have if all of $i$'s neighbors also have the largest value of $\mathbf x$ on $i$'s component.
Inductively, we show that every single vertex in $i$'s component has the largest value; therefore $\mathbf x$ is constant on the components of the graph; therefore it's spanned by the eigenvectors we've already found.
For eigenvectors of $-d$, nearly the same reasoning applies, except that we should choose $i$ so that $|x_i|$ is largest, and we have the twist that in order to reach $(A\mathbf x)_i = -d \cdot x_i$, every one of $i$'s neighbors should have the same value of $\mathbf x$, but with opposite sign. So on every component, $\mathbf x$ is either $0$, or it has a constant value up to sign, and we can get a bipartition of that component by looking at the sign. Once again, we conclude that $\mathbf x$ is spanned by the eigenvectors we've already found.
We can also use similar reasoning to show that no eigenvalue can be outside the range $[-d,d]$, but this answer is already very long so I'll just say that this is also an immediate consequence of the Gershgorin circle theorem, whether or not there are loops or parallel edges - simply because every row is nonnegative and sums to $d$.