Prove that there is a vertex in the tree from which exactly one edge emerges (such a vertex is called a hanging top).
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.
On the plane 100 circles are given, which make up a connected figure (that is, not falling apart into pieces). Prove that this figure can be drawn without taking the pencil off of the paper and going over any line twice.
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.
Each of the 102 pupils of one school is friends with at least 68 others. Prove that among them there are four who have the same number of friends.
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.