Finding a tight upperbound

Question

A call graph $G = \{V,E\}$ on phone metadata has a vertex $v \in V$ for each phone number and an edge $\{v,w\} \in E$ if there has been a phone call between $v$ and $w$. One can monitor calls of a set $S \subseteq V$ of authorized seeds. You can also investigate vertices at a distance $3$ or less from a seed(in other words three or fewer hops away). Assume $|S| = 300$ and each phone has had contact with exactly $100$ others. Under these assumptions give a tight upperbound on the number of phone numbers about which warrantless queries are permitted.

Answer 1

The set of seeds, $S$, contains $300$ vertices. The absolute upper bound on the number of phone numbers on which we can perform a warrantless query is $300 + (300 \cdot 100) + (300 \cdot 100 \cdot 99) + (300 \cdot 100 \cdot 99 \cdot 99) = 297030300$.

Reasoning:

We can take our seed set $S$. Assume none of the seeds are connected. Then we have $300$ vertices we can query. Now assume that each $s \in S$ is connected to $100$ distinct vertices. This gives another $300 \cdot 100$ vertices we can query: call this set $P$.

Now take each one of these vertices in $P$. They are also all connected to another 100 vertices. In each case, however, they will connect to one vertex among our original $300$ seeds. So from each of our current vertices in $P$, we can only query another $99$ new vertices. So we add $300 \cdot 100 \cdot 99$ vertices.

The step for the last hop is identical to the one described in the paragraph above.