Lower bound for smallest eigenvalue of symmetric doubly-stochastic Metropolis-Hasting transition matrix For my master's thesis research, I stumbled upon a question concerning the  Metropolis-Hasting transition matrix $W$.
Context $\quad$
Let me start with some context. I consider connected undirected graphs $G=(V,E)$; here $V=\{1,\ldots, M\}$ and $E$ is the edge set. I denote the neighbor sets by $\mathcal{N}_i$ and the degree of each node by $d_i$. In this context, I consider the Metropolis-Hasting transition matrix $W=[w_{ij}]$, defined by:
\begin{equation*}\label{eq:N}
w_{ij} :=
 \left\{
 \begin{array}{ll}
  \frac{1}{\max\{d_i, d_j\}+1} & \text{if} \: j \in \mathcal{N}_i, \\
  1-\sum_{j\in\mathcal{N}_i}w_{ij} & \text{if} \: j=i, \\
  0 & \text{otherwise}.
 \end{array}
 \right. 
\end{equation*}
It is known that this matrix is symmetric doubly stochastic, such that we have real eigenvalues $1=\lambda_1>\lambda_2\geq \cdots\geq \lambda_M > -1$. 
Question $\quad$ Now, i would like to show a sharper lower bound for $\lambda_M$, namely: $$\lambda_M\geq-\frac{1}{2}.$$
I don't know if this is true actually, but I considered (in Matlab) many randomly produced graphs with $M=100$. I varied the amount of edges from $0.05k_\max$ up to $0.9k_\max$, where $k_\max=\frac{1}{2}(M^2-M)$. In this way I considered over $10\:000$ matrices, and there was no counter example found. Otherwise, if there is a way to find a counter example then that would be helpful as well.
Findings so far $\quad$ I came up with an alternative formulation, using the definition for the field of values. It can be shown that it is equivalent to show that:
$$\sum_{i=1}^M\left( \: \sum_{j\in \mathcal{N}_i} \frac{x_i^2 - x_ix_j}{\max\{d_i,d_j\}+1} \right) = \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} \leq \frac{3}{2},$$
for any $x = [x_i] \in \mathbb{R}^M$ with $x^Tx =\sum_{i=1}^Mx_i^2=1$. Here the equality sign is not to difficult to prove, but the upper bound is. Does this maybe bring any ideas to mind for somebody? I got stuck here and could really use some help!

Edited on June 1, 2016 $\quad$ I am still working on this problem and this is what I am at now. So obviously, I want to relate the problem to relevant graph matrices and in the specific case that $d := d_1 = d_2 = \cdots = d_M$ this is easy. Namely, we can write $W$ as:
$$W = I - \tilde{D}^{-\frac{1}{2}}L\tilde{D}^{-\frac{1}{2}} = I - \tilde{D}^{-1}L, \quad \text{with} \quad \tilde{D} = D + I.$$
In this specific case we simply have $\tilde{D}=(d+1)I$. In all other cases (arbitrary $d_i$), I hope to show that either:
$$(i) \quad x^TWx \geq 1 - x^T\tilde{D}^{-\frac{1}{2}}L\tilde{D}^{-\frac{1}{2}}x,$$
or:
$$(ii) \quad x^TWx \geq 1 - x^T\tilde{D}^{-1}Lx, \quad$$
for all $x$ with $\sum_{i=1}^Mx_i^2=1$ and $\sum_{i=1}^Mx_i = 0$. This equivalent to showing that either:
$$(i) \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} \leq \sum_{(i,j)\in E} \left(\frac{x_i}{\sqrt{d_i+1}}-\frac{x_j}{\sqrt{d_j+1}}\right)^2 $$
or:
$$(ii) \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} \leq \sum_{(i,j)\in E} \left(\frac{x_i^2-x_ix_j}{d_i+1}+\frac{x_j^2 - x_ix_j}{d_j+1}\right) $$
By the way, you are free to consider edges in $E$ as either $(i,j)$ or $(j,i)$, so you may assume w.l.o.g. that:
$$\sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} = \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{d_i+1},$$
where $d_i\geq d_j$ for each edge. Unfortunately, element-wise comparison for both (i) and (ii) does not work for any $x$ that satisfies the constraints.  
edit some plus and minus signs are corrected
 A: One way of obtaining a simple lower bound (strictly larger than $-1$) is the following: consider the Gershgorin circles $G_i$ given by
$$G_i = \left\{z \in \mathbb{C} : |z - W_{ii}| \le R_i  \right\}$$
where $R_i$ are the off-diagonal absolute row sums of $W$. Since the elements of $W$ are all non-negative, it follows that
$$ R_i = \sum_{j \in \mathcal{N}_i} \frac{1}{\max\{d_i, d_j\} + 1} \le  \sum_{j\in\mathcal{N}_i} \frac{1}{d_i + 1} = \frac{d_i}{d_i+1}.$$
Moreover $W_{ii} = 1 - R_i$ from which it follows that
$$\lambda \in \bigcup_{i=1}^m [1 - 2R_i, 1] \subset \left[-\frac{d_\text{max} - 1}{d_\text{max} + 1}, 1\right].$$
This bound is not very sharp though. Consider for instance $d_1 =\ldots = d_m  = m - 1$, then $W$ has eigenvalues
$$\lambda_1 = 1, \lambda_2 = \ldots = \lambda_{m} = 0,$$ 
however the lower bound tends to $-1$ as $m$ gets larger.
A: Here is the relief to my question: It is (unfortunately for me) simply not true. As mentioned by Ronn3y, there is always a lower bound of $-\frac{d_\max-1}{d_\min+1}$ but there exists an example for which the the bound is sharp. Consider a complete bipartite graph with two sets of $d$ vertices (so each vertex has a common degree $d=d_\min=d_\max$), then the Metropolis-Hasting matrix is given by:
\begin{equation}
W = \frac{1}{d+1}
\begin{bmatrix}
I_d & J_d \\
J_d & I_d
\end{bmatrix},
\end{equation}
with $I_d, J_d \in \mathbb{R}^{d\times d}$; $I_d$ is the identity matrix and $J_d:=\mathbf{\mathbf{1}_d\mathbf{1}_d^T}$ is the matrix of ones ($\mathbf{1}_d \in \mathbb{R}^d$ is the vector of ones). Then we claim that $\lambda = -\frac{d-1}{d+1}$ is an eigenvalue; first we observe
\begin{equation}
W - \lambda I = \frac{1}{d+1}
\begin{bmatrix}
I_d & J_d \\
J_d & I_d
\end{bmatrix} + \frac{d-1}{d+1}
\begin{bmatrix}
I_d & 0_d \\
0_d & I_d
\end{bmatrix}
= \frac{1}{d+1}
\begin{bmatrix}
dI_d & J_d \\
J_d & dI_d
\end{bmatrix}.
\end{equation}
It is straighforward to see that a corresponding eigenvector is given by:
\begin{equation}
v =
\begin{bmatrix}
\:\:\mathbf{1}_d \\
-\mathbf{1}_d
\end{bmatrix}.
\end{equation}
