Ответ: нет, не может

Задача №2. Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

Решение. Повторим ту же идею: изобразим ситуацию из условия задачи на рисунке. Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию – отрезок или часть кривой, соединяющая конкретные точки – имена (рисунок справа). Если подсчитать число линий, изображенных на рисунке, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.

Ответ: всего было сделано 10 рукопожатий.

Задача №3. Гарри Поттер умеет превращать жабу в принцессу, гриб в жабу и грушу, грушу в яблоко, огрызок от яблока в котёнка и ёжика, котёнка в грушу или яблоко, ёжика в грушу, а яблоко – только в огрызок. Сейчас у него есть яблоко. Сможет  ли он превратить его в принцессу?

Решение. Поставив в соответствие каждому объекту точку и соединив точки, связанные отношением «превращение» линией, получим граф, в котором объекты «яблоко» и «принцесса» не связаны между собой.

Ответ: нет, нельзя.

Задача №4. В стране Цифра есть девять городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Два города соединены авиалинией только в том случае, если двузначное число,  составленное из цифр-названий этих городов, делиться на 3. Можно ли добраться из  города 1 в город 9?

Решение. Построим граф: города изобразим вершинами графа, а авиалинии –  ребрами. Вершины 3, 5, 9 связаны между собой, но не связаны с остальными. Значит, долететь из города 1 в город 9 нельзя.

Ответ: нет, нельзя.

Задача №5. На концерте каждую песню исполняли двое артистов, и никакая пара не выступала вместе более одного раза. Всего было 12 артистов, каждый выступил по 5 раз. Сколько было песен?

Решение. Рассмотрим граф, вершинами которого являются выступавшие артисты. Соединим пару артистов ребром, если они вместе пели. Получим граф с 12 вершинами степени 5, каждой песне соответствует ребро. Аналогично предыдущему примеру, в графе (12 · 5): 2 = 30 рёбер, то есть было 30 песен.

Ответ: 30 песен.