Let $G_n=(V_n,E_n)$ be an *Erdos-Rényi random graph*, precisely the vertex set is $V_n=(1,\dots,n)$ and the edge set is $E_n=(ij\in\mathcal{P}_2(V_n)\ |\ \epsilon_{ij}=1)$ where $(\epsilon_{ij})_{ij}$ are i.i.d. random variables with distribution $\textrm{Bernoulli}(c/N)$ .

It is known that $(G_n)_{n\in\mathbb{N}}$ locally converges to tree. I'm trying to prove this fact "by hands". The part which gives me some troubles is the concentration of measure. I state precisely my problem.

Fix $r\in\mathbb{N}$ and $(T,o)$ a finite rooted tree with at most $r$ generations. For any vertex $v\in V_n$ consider $B_{G_n}(v,r)$, the rooted sub-graph of $G_n$ induced by the vertices at graph-distance $\leq r$ from $v$. Consider the following random variable

$$M_n:=\frac{1}{n}\sum_{v=1}^{n}\chi(B_{G_n}(v,r)\equiv(T,o))\ ,$$ where $\chi(A)$ is the indicator function of the event $A$. And consider its expectation

$$\mathbb{E}[M_n]=\frac{1}{n}\sum_{v=1}^{n}\mathbb{P}(B_{G_n}(v,r)\equiv(T,o))\ .$$

I would like to prove that

$$|M_n-\mathbb{E}[M_n]|\xrightarrow[n\to\infty]{}0\ \ a.s.$$

Any idea? I tryed to consider a Doob martingale, exposing vertex by vertex, and to bound its differences in order to apply Azuma-Hoeffding inequality. But did not manage to find a useful bound. Can you help me?

**Edit.** I write more clearly the way I've tried. Fix $n\in\mathbb{N}$.
Define the filtration which at each step let you know the subgraph of $G_n$ induced by the first $i$ vertices:
$$\mathcal{F_1}:=(\Omega,\emptyset),\ \ \mathcal{F_i}:=\mathcal{F_{i-1}}\cup\sigma(\epsilon_{i1},\epsilon_{i2},\dots,\epsilon_{i(i-1)})\ \ \forall i=2,\dots,n.$$
Then define the following Doob martingale:
$$A_i:=\mathbb{E}[M_n|\mathcal{F_i}]\ \ \forall i=1,\dots,n$$
noticing that $A_n=M_n$ and $A_0=\mathbb{E}[M_n]$.
Now if one finds a $c_n>0$ such that $n\ c_n^2\xrightarrow[n\to\infty]{}0$ (fast enough) and
$$|A_i-A_{i-1}| < c_n\ \ \forall i=2,\dots,n$$
then by the Azuma-Hoeffding inequality one obtains that
$$\mathbb{P}(|M_n-\mathbb{E}[M_n]|>t)\ \leq\ 2\ \exp(-\frac{t^2}{2\ n\ c_n^2})\ \ \forall t>0$$
which allows to conclude thanks to Borel-Cantelli lemma.
The problem is bounding $|A_i-A_{i-1}|$.

**Edit2.** Let $d$ be the maximum degree of the tree $T$. Note that in general if two graphs $G,\tilde{G}$ differ only for one edge (i.e. $G$ contains a given edge $ij$ while $G'$ does not), then the two sums
$$\phi_G:=\sum_{v=1}^n\chi(B_{G}(v,r)\equiv(T,o))\ \ ,\ \ \phi_{\tilde{G}}:=\sum_{v=1}^n\chi(B_{\tilde{G}}(v,r)\equiv(T,o))$$
may differ at most for $2 \sum_{l=0}^r d^l$ terms (this is an upper bound for the number of vertices $v$ which can be reached from $i$ or $j$ by a walk of lenght $l\leq r$ completely made of vertces with degree $\leq d$).

Now what happens to $|\phi_G-\phi_{\tilde{G}}|$ if instead the graphs $G,\tilde{G}$ differ for one vertex (i.e. for some edges attached to a given vertex $i$)? I fear the previous bound explodes becoming unuseful in the Azuma-Hoeffding inequality... Am I right?

Maybe is there a way to exploit the fact that in a Erdos-Rényi graph the edges are not too much (precisely $|E_n|/n\xrightarrow[n\to\infty]{}c/2\ a.s.$)?