  Let $G$ be an infinite, edge- and vertex-weighted graph with certain
reasonable restrictions. We construct the heat kernel of the associated
Laplacian using an adaptation of the parametrix approach due to
Minakshisundaram-Pleijel in the setting of Riemannian geometry. This is partly
motivated by the wish to relate the heat kernels of a graph and a subgraph, or
of a domain and a discretization of it. As an application, assuming that the
graph is locally finite, we express the heat kernel $H_G(x,y;t)$ as a Taylor
series with the lead term being $a(x,y)t^r$, where $r$ is the combinatorial
distance between $x$ and $y$ and $a(x,y)$ depends (explicitly) upon edge and
vertex weights. In the case $G$ is the regular $(q+1)$-tree with $q\geq 1$, our
construction reproves different explicit formulas due to Chung-Yau and to
Chinta-Jorgenson-Karlsson. Assuming uniform boundedness of the combinatorial
vertex degree, we show that a dilated Gaussian depending on any distance metric
on $G$, which is uniformly bounded from below can be taken as a parametrix in
our construction. Our work extends in part the recent articles [LNY21, CJKS23]
in that the graphs are infinite and weighted.
