Laplacian of an infinite graph and connected components 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!
 A: As Uri Bader points out, the infinite tree has an infinitely dimensional space of harmonic functions, so this is an answer to the philosophical part of the question: The way you prove that all harmonic functions on a finite graph are constant is by using a maximum principle (the value of a function at a vertex is the average over the neighbors, so if there is a vertex where the value of the function is maximal, the function must assume the same value on all the neighbors, etc. However, a function on an infinite set need not assume its supremum, which is where the argument breaks down.
A: 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).
