We derive an explicit formula for the fundamental solution KTq+1(x,x0;t) to the discrete-time diffusion equation on the (q+1)-regular tree Tq+1 in terms of the discrete I-Bessel function. We then use the formula to derive an explicit expression for the fundamental solution KX(x,x0;t) to the discrete-time diffusion equation on any (q+1)-regular graph X. Going further, we develop three applications. The first one is to derive a general trace formula that relates the spectral data on X to its topological data. Though we emphasize the results in the case when X is finite, our method also applies when X has a countably infinite number of vertices. As a second application, we obtain a closed-form expression for the return time probability distribution of the uniform random walk on any (q+1)-regular graph. The expression is obtained by relating KX(x,x0;t) to the uniform random walk on a (q+1)-regular graph. We then show that if {Xh} is a sequence of (q+1)-regular graphs whose number of vertices goes to infinity and which satisfies a certain natural geometric condition, then the limit of the return time probability distributions from {Xh} is equal to the return time probability distribution on the tree Tq+1. As a third application, we derive formulas which express the number of distinct closed irreducible walks without tails on a finite graph X in terms of moments of the spectrum of its adjacency matrix.