  We consider the problem of constructing a graph of minimum degree $k\ge 1$ in
the following controlled random graph process, introduced recently by Frieze,
Krivelevich and Michaeli. Suppose the edges of the complete graph on $n$
vertices are permuted uniformly at random. A player, Builder, sees the edges
one by one, and must decide irrevocably upon seeing each edge whether to
purchase it or not.
  Suppose Builder purchases an edge if and only if at least one endpoint has
degree less than $k$ in her graph. Frieze, Krivelevich and Michaeli observed
that this strategy succeeds in building a graph of minimum degree at least $k$
by $\tau_k$, the hitting time for having minimum degree $k$. They conjectured
that any strategy using $\epsilon n$ fewer edges, where $\epsilon>0$ is any
constant, fails with high probability.
  In this paper we disprove their conjecture. We show that for $k\ge 2$ Builder
has a strategy which purchases $n/9$ fewer edges and succeeds with high
probability in building a graph of minimum degree at least $k$ by $\tau_k$. For
$k=1$ we show that any strategy using $\epsilon n$ fewer edges fails with
probability bounded away from 0, and exhibit such a strategy that succeeds with
probability bounded away from 0.
