# How long does it take for every node of a graph to become infected?

Consider the following stochastic process.

We begin with an undirected graph on $n$ vertices, exactly one of which is ''infected.'' Now at every time step, each infected node infects one of its non-infected neighbors uniformly at random. For example, if a given node has $3$ neighbors that are infected and $5$ that are not, then it infects exactly one of those latter $5$, each of which has probability $1/5$ of being the one chosen.

Now its clear that after $n-1$ steps every node becomes infected, since at every step at least one non-infected node becomes infected. However, I suspect that the infection actually spreads faster, because as the number of infected nodes grows, more and more non-infected nodes become infected at every stage.

My question: Is it actually true that every node is infected after $O(D)$ steps, where $D$ is the diameter of the graph?

-

Consider a tree of $n$ layers where each node at layer $n$ (up to $n-1$)has $n$ branches leading upward. The last node will be infected after $1+2+3 \ldots +(n-1)=\frac{n(n-1)}{2}$, but the diameter is $2n-2$