Prove that there is no graph with five vertices whose degrees are equal to 4, 4, 4, 4, 2.
Prove that there exists a graph with 2n vertices whose degrees are \(1, 1, 2, 2, \dots , n, n\).
a) they have 10 vertices, the degree of each of which is equal to 9?
b) they have 8 vertices, the degree of each of which is equal to 3?
c) are they connected, without cycles and contain 6 edges?
Prove that a graph, in which every two vertices are connected by exactly one simple path, is a tree.
Prove that, in a tree, every two vertices are connected by exactly one simple path.
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.
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.