Q:

Surprising connection between linear algebra and graph theory

What is the intuition for linear algebra being such an effective tool to resolve questions regarding graphs?  
For example, one can determine if a given graph is connected by computing its Laplacian and checking if the second smallest eigenvalue is greater than zero (the so called Fiedler's eigenvalue). 
It seems surprising to me that some questions about graphs, which are inherently discrete combinatorial structures, can be resolved by means of linear algebra.  What is the intuition behind this connection?  

A:

I think the basic point of contact between graph theory and linear algebra is the notion of a random walk.   Given an initial probability distribution $p$ on the vertex set $V$ of a graph (though of as a vector in $\mathbb{R}^{|V|}$), the probabilities of hitting different vertices after $k$ steps of a random walk are given by $W^k p$ where $W = A D^{-1}$ (with $A$ the adjacency matrix and $D$ the degree matrix).   This suggests that the spectral theory of $W$ is going to be relevant to dynamical questions on graphs, and the (normalized) Laplacian is just $D^{-1/2}(I - W)D^{1/2}$.  (The point of the normalization is so that eigenvalues for different graphs can be compared). 
You ask specifically why spectral theory for the Laplacian helps measure the connectivity of a graph.   Let's first note that it is possible to use random walks to answer this question.   Suppose a graph is very loosely connected, meaning it can be divided into two pieces which each have many internal connections but very few external connections.   Pick any vertex and start doing random walks of various lengths starting at that vertex.   Intuitively, you expect that these random walks will be much more likely to visit vertices in the same piece as the starting vertex and much less likely to visit vertices in the other piece, and this intuition can be made precise. 
Of course you will still probably see vertices with high degree more often then you will see vertices with low degree, so you should compare the random walk probabilities to the degree vector of the graph (normalized so that it is a probability distribution).   The normalized degree vector is an eigenvector for $W$ with eigenvalue $1$, so it is not unreasonable to expect that the small eigenvalues of the Laplacian (which is conjugate to $I - W$) will carry similar information. 
A question you might ask is: why use the Laplacian at all if the intuition comes from random walks?   The first answer is historical: the theorem relating the connectivity of graphs to the spectral theory of the Laplacian began as the Cheeger inequality, a theorem relating connectivity of Riemannian manifolds to the spectral theory of the Riemannian Laplacian operator (the two theorems have nearly identical proofs).   A more substantive answer is that for any vector $f \in \mathbb{R}^{|V|}$ we have:
$$\langle Lf, f \rangle = \sum_{u \sim v} (f(u) - f(v))^2$$
which is a particularly simple quadratic form on the graph, and thus linear algebra and spectral theory for $L$ is quite simple (and the estimates are pretty sharp).