There are 30 people, among which some are friends. Prove that the number of people who have an odd number of friends is even.
In a circle, each member has one friend and one enemy. Prove that
a) the number of members is even.
b) the circle can be divided into two neutral circles.
In some country 89 roads emerge from the capital, from the city of Dalny – one road, from the remaining 1988 cities – 20 roads (in each).
Prove that from the capital you can drive to Dalny.
Out of a whole 100-vertex graph, 98 edges were removed. Prove that the remaining ones were connected.
25 cells were coloured in on a sheet of squared paper. Can each of them have an odd number of coloured in neighbouring cells?
Can the degrees of vertices in the graph be equal to:
a) 8, 6, 5, 4, 4, 3, 2, 2?
b) 7, 7, 6, 5, 4, 2, 2, 1?
c) 6, 6, 6, 5, 5, 3, 2, 2?
In the graph, each vertex is either blue or green. Each blue vertex is linked to five blue and ten green vertices, and each green vertex is linked to nine blue and six green vertices. Which vertices are there more of – blue or green ones?
In a graph there are 100 vertices, and the degree of each of them is not less than 50. Prove that the graph is connected.
In a graph, three edges emerge from each vertex. Can there be a 1990 edges in this graph?
A class has more than 32, but less than 40 people. Every boy is friends with three girls, and every girl is friends with five boys. How many people are there in the class?