A short proof of interlacing inequalities on normalized Laplacians (Q2369039)

For a finite simple connected graph \(G\) we denote by \({\mathcal L}(G)\) the matrix whose rows and columns are indexed by vertices of \(G\), whose diagonal entries are \(1\), and whose non-diagonal entries are \(-1/{\sqrt{d_ud_v}}\), if \(u\) and \(v\) are adjacent, and \(0\) otherwise. The matrix \({\mathcal L}(G)\) is called the Laplacian of \(G\), it plays a very important role in the spectral graph theory (see [\textit{F. R. K. Chung}, Spectral graph theory (Regional Conference Series in Mathematics. 92. Providence, RI: American Mathematical Society (AMS)) (1997; Zbl 0867.05046)]). The paper contains a short and using only elementary linear algebra proof of the following interesting result of \textit{G. Chen} et al. [SIAM J. Discrete Math. 18, 353--361 (2004; Zbl 1079.05054)]: Suppose that \(H\) is a connected graph obtained from the graph \(G\) by removing an edge. Let \(\lambda_1\geq\dots\geq\lambda_n\) and \(\mu_1\geq\dots\geq\mu_n\) be eigenvalues of \({\mathcal L}(G)\) and \({\mathcal L}(H)\), respectively. Set \(\lambda_0=2\) and \(\lambda_{n+1}=0\). Then \(\lambda_{j-1}\geq\mu_j\geq\lambda_{j+1}\) for \(j=1,\dots,n\).