Prove that there exists a graph with 2n vertices whose degrees are \(1, 1, 2, 2, \dots , n, n\).
In a graph, all the vertices have degree of 3. Prove that there is a cycle in it.
There are seven lakes in some country, connected by ten non-overlapping canals, and each lake can be reached from any other. How many islands are there in this country?
Prove that for a flat graph the inequality \(2E \geq 3F\) is valid.
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.
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.
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\).