Олимпиадные задачи из источника «глава 13. Графы-2» для 6-8 класса - сложность 1 с решениями

В некотором государстве каждый город соединён с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?

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

Докажите, что в дереве каждые две вершины соединены ровно одним простым путем.

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

Докажите, что не существует графа без петель и кратных рёбер с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.