Задача 1: Сколько рёбер в полном графе с 20 вершинами?

Решение: 190

Задача 2: Сколько всего рёбер в графе, степени вершин которого равны 3, 4, 5, 3, 4, 5, 3, 4, 5 ?

Решение: 18

Задача 3: В дереве имеется 100 вершин степени 5, 100 вершин степени 3, а остальные – висячие. Сколько висячих вершин в этом дереве?

Решение: 402

Задача 4: Какое число рёбер нужно убрать из полного графа с 15 вершинами, чтобы оставить его скелет?

Решение: 91

Задача 5: Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?

Решение: 14

Задача 6: Лес состоит из 10 деревьев. Всего в лесу 200 вершин. Сколько в нем рёбер?

Решение: 190

Задача 7: Однажды Рома сказал: «Если степень каждой вершины 100-вершинного графа не меньше N, то этот граф связен». При каком наименьшем значении N Рома сможет это доказать, если известно, что его не зря взяли в профи?

Решение: 50

Задача 8: Из нескольких кусочков проволоки спаяна проволочная решетка 8 × 8 клеток. Какое наименьшее число кусочков для этого могло потребоваться?

Решение: 14

Задача 9: Во дворе живут 4 пёсика: Бобик, Робик, Тобик и Толстолобик. Каждому из них случалось драться с кем-нибудь из остальных, причём у Бобика, Робика и Тобика число тех, с кем они дрались – разное. Со сколькими собаками двора дрался Толстолобик?

Решение: 2

Задача 10: В стране 6 городов. Авиасообщение осуществляют несколько авиакомпаний. Каждая обслуживает 3 авиалинии, связывающие попарно некоторые три города (между двумя городами могут летать самолеты нескольких компаний). Каждые два города связаны по крайней мере одной линией. При каком наименьшем числе компаний это возможно?

Решение: 6

Задача 11: Каждое ребро графа покрасили в синий или зелёный цвет так, что ни из одной вершины не выходит двух одноцветных рёбер. Синих рёбер оказалось на 5 больше, чем зелёных. Какое наименьшее число компонент связности может иметь этот граф?

Решение: 5