the sample path ${\bf X}^*[0,t+1]$ and denote by $\tilde{t}_{v_r}^R$ the recovery time of node $v_r$ in ${\bf X}^*[0,t+1]$. We now construct a sample path $\bar{\bf X}[0,t]$ as follows:

-   If $\tilde{t}_{v_r}^R>t+1,$ i.e., $v_r$ is an infected node, then $\bar{t}_{v_r}^R>t,$ where $\bar{t}_{v_r}^R$ is the recovery time of $v_r$ in $\bar{\bf X}[0,t].$

-   If $\tilde{t}_{v_r}^R\leq t,$ we choose $\bar{t}_{v_r}^R=\tilde{t}_{v_r}^R.$

-   If $\tilde{t}_{v_r}^R= t+1,$ we choose $\bar{t}_{v_r}^R=t.$

We further complete $\bar{\bf X}[0,t]$ by having optimal ones on ${\cal T}^h$ and constructing the ones in ${\cal T}^i$ following step 2.b. According to steps 2.a and 2.b, it is easy to verify that $\bar{\bf X}[0,t]$ occurs with a higher probability than ${\bf X}^*[0,t+1].$ Therefore, we conclude that inequality (\[eqn:3\]) holds for $k=n+1,$ hence for any $k$ according to the principle of induction.

[**Step 3**]{} Repeatedly applying inequality (\[eqn:3\]), we obtain that $t^*_{v_r}$ is the minimum amount of time required to produce the observed infection topology. The minimum time required is equal to the maximum distance from $v_r$ to an infected node. Therefore, the lemma holds.

The Sample Path Based Estimator
-------------------------------

After deriving $t_v^*$, we have a unique $t_v^*$ for each $v\in {\cal V}$. The next lemma states that the optimal sample path starting from 