  Let $\Gamma$ be a locally finite graph, $L$ the normalized Laplacian of
$\Gamma$. If $\Gamma$ is uniformy locally finite, i.e. if each vertex has no
more than $d$ adjacent vertices, then the matrix of $L$ (with respect to the
standard basis) has no more than $d+1$ non-zero entries in each row and in each
column. We consider the class of locally finite graphs, for which the Laplacian
can be approximated by matrices of this type with arbitrary $d$. We provide
examples of locally finite graphs which are or are not in this class, and show
that the graphs from this class share certain regularity property: vertices of
high degree cannot have too many adjacent vertices of low degree.
