For a finite graph, we can find the number of connected components of the graph as $\dim \ker L$, where $L = D – A$ is the Laplacian matrix.
Does this still hold true for an infinite graph where every vertex has finite degree (if we consider the domain and codomain of $L$ to be sequence space $\Bbb{R}^\infty$)?
If not, what about if every vertex has bounded degree (i.e. there exists $M$ so that $d(v) \leq M$ for all $v \in V(G)$)?
Follow-up: Eric Wofsey has given an explicit example where $\dim \ker L$ is strictly greater than the number of connected components. Is it possible to go the other way, and have $\dim \ker L$ be strictly less? Or is $\dim \ker L$ always an upper bound?
Follow-up to the follow-up: How may the number of connected components of an infinite graph with bounded degree, or where every vertex has finite degree, be calculated from its adjacency matrix or its Laplacian matrix?
Best Answer
No. For instance, consider the graph whose vertices are integers with $n$ adjacent to $n-1$ and $n+1$ for each $n$. Then a sequence $s:\mathbb{Z}\to\mathbb{R}$ is in the kernel of the Laplacian iff $s(n)$ is the average of $s(n-1)$ and $s(n+1)$ for each $n$. Now given any two values for $s(0)$ and $s(1)$, you can uniquely determine the values of $s(n)$ for all $n$ by the recurrence $s(n+1)=2s(n)-s(n-1)$ (explicitly, the solutions to this recurrence are the linear sequences $s(n)=an+b$ where $a$ and $b$ are arbitrary parameters). So $\dim\ker L=2$ , even though the graph has only one connected component.