Can there be exactly 100 roads in a state in which three roads leave each city?
John, coming back from Disneyland, told me that there are seven islands on the enchanted lake, each of which is lead to by one, three or five bridges. Is it true that at least one of these bridges necessarily leads to the shore of the lake?
Prove that the number of people who have ever lived on Earth and who shook hands an odd number of times is even.
Is it possible to draw 9 segments on a plane so that each intersects exactly three others?
In the country Seven there are 15 cities, each of which is connected by roads with no less than seven other cities. Prove that from every city you can get to any other city (possibly passing through other cities).
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.