TLDR: The multiplicity of $0$ as an eigenvalue of $L$ gives the number of connected components in the graph. The eigenspace of $0$ gives us a way to partition the graph. The application to your problem is at the end of the post.
One common proof of this uses two facts:
- $\lambda_2$, often called the algebraic connectivity of the graph, is positive if and only if $L$ has exactly one connected component.
- The spectrum of a block diagonal matrix is the union (with multiplicty) of the spectra of the blocks.
Each connected component corresponds to a block of $L$ (we could permute $A$ and $L$ to show the blocks without changing anything since this is just a relabeling of the graph), so $L$ will have one block per component and each component contributes exactly one eigenvalue of $0$. I'll use $K$ as the number of components.
This tells us how many components there are, and the eigenvectors of zero tell us how to partition the graph. We can connect the two by using the result that
$$
x^T L x = \sum_{u\sim v} A_{uv}(x_u - x_v)^2.
$$
A vector $x$ can be thought of as assigning a value to each node in the graph with $x_v$ being the value for node $v \in V$. $x^T L x$ tell us if $x$ tends to have big changes between well-connected nodes. I like to picture this by thinking of the graph as a collection of balls and springs and initially placing it flat on a table. Then, given some $x$, we raise or lower each node $v$ to a height of $x_v$ (lowering it if $x_v< 0$) and then $x^T L x$ is like how much stress this configuration has. If we have nodes with strong springs between them that we are moving far apart, i.e. $A_{uv}$ and $(x_u - x_v)^2$ are large, then the configuration is high stress. Minimizing $x^T L x$ is like finding a way to raise some nodes and lower others so that the graph is relatively stress-free and changes in $x$ happen over weak edges.
We always have one stress-free assignment: assign every node the same value. This shows that we can always achieve $x^T L x = 0$, which confirms how every component has an eigenvalue of $0$ by itself. If $K=1$ then the only stress-free assignments are constant vectors. If we are required to cut the graph into two pieces then we will incur some loss, but one good way to do it is to use an eigenvector of $\lambda_2$ which is what the Fiedler vector is. I'll denote such a vector by $f$. Since $0 = \lambda_1 < \lambda_2$ in this case we know $f^T\mathbf 1 = 0$ (this is due to eigenspaces of different eigenvalues being orthogonal) so this means $f$ will have some positive values and some negative values. $f$ makes $x \mapsto x^T L x$ as small as we can while being orthogonal to $\mathbf 1$, so it finds the least stressful non-trivial (i.e. we don't just put everything in th same cluster) partition of the graph, and $\lambda_2$ is the associated loss which is why $\lambda_2$ being small means the graph is less connected.
But if $K>1$ then we'll have a more interesting situation. Now we'll have a $K$-dimensional solution space to $x^T L x = 0$. There are lots of bases for this space, but one appealing one is$\newcommand{\one}{\mathbf 1}$$\{\one_{C_1}, \dots, \one_{C_K}\}$ where $\one_{C_j}$ denotes the vector that is $1$ on the nodes in component $j$ and $0$ elsewhere. Effectively these are component indicators. Each one of these gives a totally stress-free configuration because there are no springs between $C_i$ and $C_j$ for $i\neq j$.
The only trick here is that there are lots of bases for this eigenspace so we don't always get this exact one and it may not be easy for a human to read off the components from the eigenvectors. But if we finish the spectral clustering algorithm with k-means then we'll recover the components since no matter what basis we choose, it will be constant on each cluster so the nodes within a component will all be mapped to the same point and k-means will effortlessly collect them.
Applying this to your problem: you have $K=4$ and your four eigenvectors of $0$ let us easily read off the components. The first eigenvector is constant on nodes 1,2, and 3 and shows that's $C_1$. Then the next three eigenvectors are indicators for single nodes so we have one component of three nodes and then the other 3 components are just of isolated nodes with no neighbors. The self-degree of node 6 doesn't matter for this.
For more reading, Luxburg's Tutorial on Spectral Clustering is a fantastic and popular resource. Fan Chung's Spectral Graph Theory is also great although she uses a normalized Laplacian so some results may look a little different. I also really like Daniel Spielman's writings, such as this textbook draft on spectral graph theory. Ng et al's famous paper on spectral clustering is also very helpful for the difference between the noise-free case when clustering can be perfectly achieved vs. the more realistic noisy case.
