  We prove the Li-Yau gradient estimate for the heat kernel on graphs. The only
assumption is a variant of the curvature-dimension inequality, which is purely
local, and can be considered as a new notion of curvature for graphs. We
compute this curvature for lattices and trees and conclude that it behaves more
naturally than the already existing notions of curvature. Moreover, we show
that if a graph has non-negative curvature then it has polynomial volume
growth.
  We also derive Harnack inequalities and heat kernel bounds from the gradient
estimate, and show how it can be used to strengthen the classical Buser
inequality relating the spectral gap and the Cheeger constant of a graph.
