  We study the existence and uniqueness of the heat kernel on infinite, locally
finite, connected graphs. For general graphs, a uniqueness criterion, shown to
be optimal, is given in terms of the maximal valence on spheres about a fixed
vertex. A sufficient condition for non-uniqueness is also presented.
Furthermore, we give a lower bound on the bottom of the spectrum of the
discrete Laplacian and use this bound to give a condition ensuring that the
essential spectrum of the Laplacian is empty.
