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$.

Thirteen boys and girls met to play a football match. Eleven of them shook hands with everybody else in the group. The last two shook hands with everybody else but not each other, because they were siblings and arrived together. How many handshakes took place?

The city of Konigsberg has seven bridges as depicted on the layout below. $$\text{includegraphics}[scale=0.5]https://problems-static.s3.amazonaws.com/production/tas{k}_{i}mages/2829/WSP-000146.png$$ Is it possible for the great mathematician Leonard Euler to have an excursion in Konigsberg visiting all islands and land banks, but crossing each bridge exactly once?

There are $6$ people at a party. Each two people either know each other or not, and the knowledge goes both ways: if $A$ knows $B$, then $B$ knows $A$. Show that there either is a trio of people who all know each other or a trio of people who all don’t know each other.

An elven village in the woods has $11$ treehouses. We want to link the houses by ropes so that each house is connected to exactly $4$ others. How many ropes do we need?

Can you draw a house like the one below without lifting your pen from the paper, nor going over the same edge twice? $$\text{includegraphics}[scale=0.5]https://problems-static.s3.amazonaws.com/production/tas{k}_{i}mages/2833/WSP-000149.png$$

Last week eight heads of state, (3 presidents, 3 prime ministers and 2 emperors), got together for a conference. According to a reporter, each president shook hands with 6 heads of state, each prime minister shook hands with 4, and each emperor with 1. Is this possible?