  Consider a collection of random variables attached to the vertices of a
graph. The reconstruction problem requires to estimate one of them given `far
away' observations. Several theoretical results (and simple algorithms) are
available when their joint probability distribution is Markov with respect to a
tree. In this paper we consider the case of sequences of random graphs that
converge locally to trees. In particular, we develop a sufficient condition for
the tree and graph reconstruction problem to coincide. We apply such condition
to colorings of random graphs.
  Further, we characterize the behavior of Ising models on such graphs, both
with attractive and random interactions (respectively, `ferromagnetic' and
`spin glass').
