d $d$‐connectivity of the random graph with restricted budget

Abstract In this short note, we consider a graph process recently introduced by Frieze, Krivelevich and Michaeli. In their model, the edges of the complete graph are ordered uniformly at random and are then revealed consecutively to a player called Builder. At every round, Builder must decide if they accept the edge proposed at this round or not. We prove that, for every , Builder can construct a spanning ‐connected graph after rounds by accepting edges with probability converging to 1 as . This settles a conjecture of Frieze, Krivelevich and Michaeli.