Problems

Age
Difficulty
Found: 1941

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?

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?

In the oriented graph, there are 101 vertices. For each vertex, the number of ingoing and outgoing edges is 40. Prove that from each vertex you can get to any other, having gone along no more than three edges.

The faces of a polyhedron are coloured in two colours so that the neighbouring faces are of different colours. It is known that all of the faces except for one have a number of edges that is a multiple of 3. Prove that this one face has a multiple of 3 edges.