Connectivity of weighted graph and zero Laplacian eigenvalues

Question

Given an undirected graph $G$, and let $V$ denote its set of vertices and $E$ its set of edges. Suppose that there are no edges connecting the same vertex, and no more than one edge connecting any pair of vertices.

The adjacency matrix is \begin{equation} a_{ij} = \begin{cases} 1 & If \, (i,j) \in E \\ 0 & \textrm{Otherwise} \end{cases}, \end{equation} and the Laplacian is $L = \delta_{ij} \sum_{k} a_{ik} - a_{ij}$.

It is known that the number of connected components of $G$ is equal to the multiplicity of the zero eigenvalue of $L$.

Is this result true also for weighted undirected graphs, where \begin{equation} a_{ij} = \begin{cases} w_{ij} & If \, (i,j) \in E \\ 0 & \textrm{Otherwise} \end{cases}, \end{equation} with $w_{ij}$ some positive weight? If so, may you please give me a reference where I can find the proof for weighted graph?

Thank you

Answer 1

Start with the unweighted case. We have $L=BB^T$ where $B$ is (what I call) the incidence matrix of an orientation of $G$. So $B$ has one 1 and one $-1$ in each column with all other entries zero. The left kernel of $B$ consists of the functions on $V(G)$ that are constant on the components of $G$. Since $B$ and $BB^T$ have the same rank, we get the connection between number of components and multiplicity of 0 as an eigenvalue of $L$.

Now suppose we have a non-zero weight on each edge of $G$, and let $\Delta$ be the diagonal matrix with rows and columns indexed by $E(G)$, and with $i$-th diagonal entry equal to the weight of the $i$-th edge. Then $B\Delta B^T$ is your weighted Laplacian and, since $BB^T$ and $B\Delta B^T$ have the same rank, we're done.

Answer 2

You can simply imitate the proof in the unweighted case. The Rayleigh quotient associated to the Laplacian is:

$$R_G(f) = \frac{\langle Lf, f \rangle}{\langle f, f \rangle} = \frac{\sum_{x \sim y} (f(x) - f(y))^2 w_{x,y}}{\sum_x f(x)^2}$$

Assuming the weights are all positive we get that $R_g(f) \geq 0$ with equality if and only if $f$ is locally constant, and the dimension of the space of locally constant functions on a graph is just the number of connected components.

An additional advantage of having the formula above lying around is that you can also use it to adapt the usual proof of the Cheeger inequality to weighted graphs.