Fast winning strategies in Maker–Breaker games

We consider unbiased Maker–Breaker games played on the edge set of the complete graph K n on n vertices. Quite a few such games were researched in the literature and are known to be Makerʹs win. Here we are interested in estimating the minimum number of moves needed for Maker in order to win these games. ve the following results, for sufficiently large n:(1) can construct a Hamilton cycle within at most n + 2 moves. This improves the classical bound of 2n due to Chvátal and Erdős [V. Chvátal, P. Erdős, Biased positional games, Ann. Discrete Math. 2 (1978) 221–228] and is almost tight; can construct a perfect matching (for even n) within n / 2 + 1 moves, and this is tight; fixed k ⩾ 3 , Maker can construct a spanning k-connected graph within ( 1 + o ( 1 ) ) k n / 2 moves, and this is obviously asymptotically tight. al other related results are derived as well.