# Lower bound on the eigenvalues of the Laplacian

I am looking for a graph for which $2 d_{i} < \mu_{i}$, for some index $i$, where $\mu_{1} \leq \mu_{2} \leq \dots\leq \mu_{n}$ are the eigenvalues of the Laplacian matrix $L(G)$ and $d_{1} \leq d_{2} \leq \dots \leq d_{n}$ are the node degrees.

According to the literature and existing upper/lower bounds on the eigenvalues of the Laplacian as a function of node degrees, it seems there is a graph with this property. However, I was not able to find such a graph by generating all graph with $4, 5, \dots, 10$ vertices. Any help or advice for a possible hypothesis confirmation or rejection would be appreciated.

Related references:

• There is no example of such graphs. For this, you can use min-max theorem and the restriction to the subspace generated by vectors supported in first $i$ vertices of the graph. – Mostafa Apr 9 '18 at 14:21

This is an expanded solution based on the comment of @mostafa.

Such graphs dose not exist.

Let $L$ be the Laplacian of the graph. Suppose that diagonal elements of $L$ are sorted sequence of degrees $d_1\leq \ldots \leq d_n$. By Min-Max theorem, we have

$$\mu_i= \min_{U<\mathbb R^n,\dim(U)=i} \big\{ \max_{x \in U, \|x\|=1} x^TL x \big\}$$

So, if there exists an $i$-dimensional subspace of $\mathbb R^n$, say $U$, such that

$$\max_{x \in U, \|x\|=1} x^TL x \leq 2d_i$$ then we have $\mu_i \leq 2d_i$.

Let $U := \langle e_1,\ldots,e_i\rangle$, where $e_k$ is $k$-th element of the standard base of $\mathbb R^n$, for $k=1,\ldots,i$. Suppose that $x\in U$ and $\|x\|=1$. Note that only first $i$ elements of $x$ are nonzero. we have $$x^TL x = \sum_{ab \in E(G),a<b} (x_a-x_b)^2 \leq \sum_{ab \in E(G),a<b} 2(x_a^2+x_b^2)=2\sum_{k=1}^id_k x_k^2\leq2d_i.$$ Now the statment at hand.