Problems

There are \(16\) cities in the kingdom. Prove that it is possible to build a system of roads in such a way that one can get from any city to any other without passing through more than one city on the way, and with at most five roads coming out of each city.

A graph is a finite set of points, some of which are connected with line segments. The points of a graph are called vertices. The line segments are called edges. In this problem set we only consider graphs in which every pair of vertices is connected with one or zero edges.

In a mathematical problem, one may use vertices of a graph to represent objects in the problem, i.e. people, cities, airports, and edges of the graph represent relations between the objects such as mutual friendship, railways between cities, plane routes. As you will see in the examples below, representing the initial problem as a graph can considerably simplify the solution.

A graph is called Bipartite if it is possible to split all its vertices into two groups in such a way that there are no edges connecting vertices from the same group. Find out whic of the following graphs are bipartite and which are not:

Imagine you are a manager of a very special hotel, a hotel with an infinite number of rooms, where each room has a natural number on the door \(1,2,3,4,...\). Only one guest can stay in each room and in most cases the hotel will be initially full with no vacant rooms left.
You will have to deal with unusual situations that may occur.

Show that a bipartite graph with \(n\) vertices cannot have more than \(\frac{n^2}{4}\) edges.

In the picture below you can see the graphs of \(K_5\), the complete graph on \(5\) vertices, and \(K_{3,3}\), the complete bipartite graph on \(3\) and \(3\) vertices. A theorem states that these graphs cannot be embedded into plane, namely one cannot draw graphs \(K_5\) and \(K_{3,3}\) on a plane in such a way that there are no intersecting edges.
The question is: can you draw the graphs \(K_5\) and \(K_{3,3}\) without intersecting edges on a torus?

If we glue the opposite sides of the paper band in the same direction as on the picture, we will get a cylinder. What surface do we get, if we glue the circles of the cylinder in the same direction as well?

We start with a rectangular sheet of paper - preferably with proportions more than \(6:1\), so that it looks more like a band. For now assume that one can stretch or shrink the paper band as needed. Describe the surface we get if we start with a rectangular sheet of paper and then glue the opposite sides of the paper band in the opposite direction as in the picture.

How would you describe the surface obtained by glueing the sides of the octagon as on the picture? Sides of the same colour are glued together in the same direction as shown.

Describe the surface which we can get if we start with a rectangular sheet of paper, make a cylinder by glueing the opposite sides in the same direction and then glue the other opposite sides of the paper band in the opposite direction as on the picture.