The essence of this problem is: from the linearity of expectation (and the fact that each vertex gets chosen at most once), the following holds:

• The expected number of operations can be found as follows: find the probability for each vertex to be chosen until the graph becomes empty, then sum them up over all vertices.

Thus, we only need to find the probability for each vertex to be chosen until the graph becomes empty.

Here, we can prove the following two facts, where \(S(v) \subseteq V\) is the set of vertices from which Vertex \(v\) is reachable:

• Vertex \(v\) gets deleted when and only when a vertex in \(S(v)\) is chosen.
• Vertices in \(S(v)\) never get deleted when a vertex not in \(S(v)\) is chosen.

Thus, the probability for \(v\) to be chosen equals the probability that \(v\) is the first vertex to be chosen in \(S(v)\), which is \(\frac{1}{|S(v)|}\).

Therefore, the answer is \(\sum_{v \in V} \frac{1}{|S(v)|}\).