Let $G(V, E)$ be a simple graph with $|V|=n$, and let $h$ be an integer in $[n]$.

We repeat $h$-many times the following operation in a sequential fashion, where the graph may change at each round. We denote by $G_t(V_t, E_t)$ the graph obtained just after round $t\in [h]$ (we have thereofore $G(V,E)=G_0(V_0,E_0)$):

At each round $t=1, 2, \ldots, h$, we select uniformly at random (with replacement) $h$-many vertices from $V_t$. Let $v$ be the first vertex selected. *If* at least one of the other selected vertices is adjacent to $v$ in $G_t$, *then* we remove from $G_t$ vertex $v$ and all vertices adjacent to $v$ (together with their incident edges) -- *otherwise* $G_t(V_t,E_t)=G_{t-1}(V_{t-1},E_{t-1})$.

**Question**: In expectation over the above random process, what is the maximum number of edges in $E_h$ over all possible $2^{n \choose 2}$-many input graphs $G(V, E)$ (when $n\to\infty$)?

(*I am especially interested in finding a tight* *upper bound**for $\max_{G(V,E)}\mathbb{E}\left[|E_h|\right]$*).

**Conjecture**: The maximum value for $\mathbb{E}\left[|E_h|\right]$ is equal to $\Theta\left(\frac{n^2}{h}\right)$.

(*In particular, I cannot find any graph $G(V,E)$ for which $\mathbb{E}\left[|E_h|\right]=\omega\left(\frac{n^2}{h}\right)$*).