МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Графы

1.

Какие из следующих пяти графов изоморфны?

2.

Нарисуйте все неизоморфные друг другу графы с не более чем четырьмя вершинами.

3.

Нарисуйте граф, вершинами которого являются натураль¬ные числа от 1 до 15, а рёбрами соединены числа, одно из которых делится на другое.

4.

Постройте граф с пятью вершинами, в котором нет ни трёх попарно соединённых, ни трёх попарно несоединённых вершин.

5.

Докажите, что в каждой компании из шести человек найдутся либо три попарно знакомых, либо три попарно незнакомых человека.

6.

Укажите степени всех вершин графов из задачи 3.

Дополнительные задачи

7.

Докажите, что в графе с более чем одной вершиной есть две вершины одинаковой степени.

8.

Докажите, что сумма степеней вершин произвольного графа равна удвоенному количеству его рёбер.

Супербонус

9.

Найти наибольшее возможное количество рёбер в графе с n вершинами, если известно, что среди произвольных
а) трёх,
б*) четырёх его вершин есть две, не соединённые ребром.