For a finite graph with undirected, unweighted edges, a well-known result is that the dimension of the null space of the Laplacian matrix gives the number of connected components. Does this result apply to infinite graphs as well?


The infinite graphs I'm interested are locally finite. That is, the degree of each node is finite. In my case, the number of nodes is countably infinite, there are no self-edges, and the edges are undirected.


At least according to the PDF from this course:
<http://www.maths.nuigalway.ie/~rquinlan/linearalgebra/section3-1.pdf>


the connected components theorem does not assume anything about finite graphs. Can someone provide a reference (a paper or text) where this is explicitly discussed?


Thank You!



Laplacian of an infinite graph and connected components
For infinite (locally finite) graphs it is not true in general that the dimension of the kernel of the Laplacian is the number of connected components.


The simplest example to have in mind is the standard graph structure on $\mathbb{Z}$, which is connected, where the kernel of the Laplacian consists exactly of all arithmetic progressions - a two dimensional space.


Here we view the Laplacian as an operator on the space of all functions on the graph.
In view of this example and related phenomena, it makes sense to restrict the attention to smaller function spaces, e.g the space $\ell^\infty(V)$ consisting of all bounded function or the space $\ell^2(V)$ consisting of all square summable functions on the set of vertices of our graph, $V$.


For these spaces the kernel of the Laplacian on $\ell^{\infty}(\mathbb{Z})$ is one dimensional, as you might expect from your finite graph experience, while it is zero dimensional on $\ell^2(\mathbb{Z})$.


But the story gets more complicated for more complicated graphs and the dimension of the Laplacian might get infinite even for $\ell^{\infty}(V)$ when the graph is connected, eg when it is an infinite tree.


There is a vast literature on the subject. Google up "harmonic functions on graphs" (note that elements in the kernel of the Laplacian are called *harmonic functions*).


