At a conference there are 50 scientists, each of whom knows at least 25 other scientists at the conference. Prove that is possible to seat four of them at a round table so that everyone is sitting next to people they know.
Dan drew seven graphs on the board, each of which is a tree with six vertices. Prove that among them there are two which are isomorphic.
Each of the edges of a complete graph consisting of 6 vertices is coloured in one of two colours. Prove that there are three vertices, such that all the edges connecting them are the same colour.
Eugenie, arriving from Big-island, said that there are several lakes connected by rivers. Three rivers flow from each lake, and four rivers flow into each lake. Prove that she is wrong.
In some country there is a capital and another 100 cities. Some cities (including the capital) are connected by one-way roads. From each non-capital city 20 roads emerge, and 21 roads enter each such city. Prove that you cannot travel to the capital from any city.
Prove that on the edges of a connected graph one can arrange arrows so that from some vertex one can reach any other vertex along the arrows.
Several teams played a volleyball tournament amongst themselves. We will say that team \(A\) is better than team \(B\), if either \(A\) has either beaten team \(B\), or there exists such a team \(C\) that was beaten by \(A\), whilst \(C\) beat team \(B\).
a) Prove that there is a team that is better than all.
b) Prove that the team that won the tournament is the best.
Some two teams scored the same number of points in a volleyball tournament. Prove that there are teams \(A\), \(B\) and \(C\), in which \(A\) beat \(B\), \(B\) beat \(C\) and \(C\) beat \(A\).
In the country called Orientation a one-way traffic system was introduced on all the roads, and each city can be reached from any other one by driving on no more than two roads. One road was closed for repairs but from every city it remained possible to get to any other. Prove that for every two cities this can still be done whilst driving on no more than 3 roads.
Prove that \(\frac {1}{2} (x^2 + y^2) \geq xy\) for any \(x\) and \(y\).