Let $\mathcal{L}$ be the Laplacian matrix of a connected, undirected and unweighted graph $\mathcal{G}$ with $n$ vertices, and let $\Delta \in \mathbb{R}^{n\times n}$ be a diagonal matrix with at least one nonzero entry (for instance $\Delta=\mbox{diag}\{1,0,\cdots,0\}$).
Numerically, I can see that
$$x^T(L+\Delta)x>0$$
But I cannot prove it since both matrices, $\mathcal{L}$ and $\Delta$ are positive semidefinite.
Any thoughts?
On
Let $y \in \{0,1\}^n \setminus \{\boldsymbol{0}_n\}$ such that $\Delta := \text{diag}(y)$. Note that both $L$ and $\Delta$ are positive semi-definite, so $L+\Delta$ is also positive semi-definite at least. Consider the next matrix $$L^+ := \begin{bmatrix} \sum y_i & -y^{\rm T} \\ -y & L+\Delta \end{bmatrix},$$ which is another Laplacian on its own right, hence it is positive semi-definite. Let’s call $\mathcal{G}^+$ the graph asociated to $L^+$. Since there exists at least one single non-zero entry in $y$, then $\mathcal{G}^+$ is connected (because $\mathcal{G}$ is connected.) Then, $\mathcal{G}^+$ has got at least one spanning tree, and by Kirchhoff’s Theorem, any cofactor of $L^+$ is positive; namely, $\det(L+\Delta)>0$. Since $L+\Delta$ is both positive semi-definite and invertible (both conditions discarding the posibility of pair-wise negative eigenvalues), then $L+\Delta$ is positive definite. $\blacksquare$
More or less like the solution above, but with less theory.
If $a_{ij}$ is the weight between the vertices $i$, $j$ $$x^t \cdot L \cdot x = \sum_{i<j}a_{ij}(x_i-x_j)^2 \ge 0$$ (we knew that). We can also see for what vectors $x$ we have equality: they lie in the subspace generated by $(x^C)$, where for each $C$ connected component of the graph $x^C$ is (more or less) the characteristic function of that component. If the graph is connected that means $x$ has all components equal.
If $\Delta$ is another positive semidefinite matrix then the kernel of $(L+\Delta)$ is the intersection of the kernels of $L$ and $\Delta$. Now it's easy to see that the intersection is $(0)$ if $\Delta$ is also diagonal and non-zero.