Prove that a graph with \(n\) vertices, the degree of each of which is at least \(\frac{n-1}{2}\), is connected.
In the Far East, the only type of transport is a carpet-plane. From the capital there are 21 carpet-planes, from the city of Dalny there is one carpet-plane, and from all of the other cities there are 20. Prove that you can fly from the capital to Dalny (possibly with interchanges).
In a country coming out of each city there are 100 roads and from each city it is possible to reach any other. One road was closed for repairs. Prove that even now you can get from every city to any other.
There is a group of islands connected by bridges so that from each island one can get to any of the other islands. The tourist has bypassed all the islands, walking on each bridge exactly once. He visited the island of Three-isle three times. How many bridges are there on Three-isle if the tourist
a) did not start on it and did not finish on it?
b) started on it, but did not finish on it?
c) started on it and finished on it?
There are three groups of stones: in the first – 10, in the second – 15, in the third – 20. During one turn, you are allowed to split any pile into two smaller ones; the one who cannot make a move loses.
Numbers from 1 to 20 are written in a row. Players take turns placing pluses and minuses between these numbers. After all of the gaps are filled, the result is calculated. If it is even, then the first player wins, if it is odd, then the second player wins. Who won?
Two players take turns to put rooks on a chessboard so that the rooks cannot capture each other. The player who cannot make a move loses.
On a board there are written 10 units and 10 deuces. During a game, one is allowed to erase any two numbers and, if they are the same, write a deuce, and if they are different then they can write a one. If the last digit left on the board is a unit, then the first player won, if it is a deuce then the second player wins.
Two players in turn put coins on a round table, in such a way that they do not overlap. The player who can not make a move loses.
a) Two in turn put bishops in the cells of a chessboard. The next move must beat at least one empty cell. The bishop also beats the cell in which it is located. The player who loses is the one who cannot make a move.
b) Repeat the same, but with rooks.