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 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:

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

In a graph \(G\), we call a matching any choice of edges in \(G\) in such a way that all vertices have only one edge among chosen connected to them. A perfect matching is a matching which is arranged on all vertices of the graph.
Let \(G\) be a graph with \(2n\) vertices and all the vertices have degree at least \(n\) (the number of edges exiting the vertex). Prove that one can choose a perfect matching in \(G\).