2.3. Given an empty graph on $n>2$ vertices and a natural number $k<4$. Vasya and Petya play the following game: Vasya chooses 3 vertices and draws edges between them that do not yet exist. Then Petya erases any $k$ edges of the graph. Vasya makes the first move. Vasya wins if after Petya's turn the graph on $n$ vertices is connected. For which $k$ does Vasya win?

## Third Round
2.3. Solution. Note that if $k=3$, then Petya can leave the graph empty after each of Vasya's moves. If $k=2$, then after each of Vasya's moves, Petya can erase all edges coming out of a fixed vertex. We will prove that when $k=1$, Vasya can win. He will, as long as possible, increase the number of edges in the graph by two with each move, meaning that after both Vasya's and Petya's moves, the number of edges will increase by at least one. Note that as long as there is a vertex from which at least two edges have not been drawn, this is possible: we will choose a triangle formed by this vertex and two vertices with which it is not connected. Thus, we will obtain a graph in which the degree of each vertex $\geqslant n-2$. Such a graph will remain connected even if an edge is removed from it.

![](https://cdn.mathpix.com/cropped/2024_06_04_b1380f2021d62732a78bg-20.jpg?height=422&width=1010&top_left_y=49&top_left_x=523)

Fig. 18: to the solution of problem 2.2

![](https://cdn.mathpix.com/cropped/2024_06_04_b1380f2021d62732a78bg-20.jpg?height=466&width=968&top_left_y=618&top_left_x=544)

Fig. 19: to the solution of problem 3.2

## Third Round