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

Двузначное число делится на 2, если его последняя цифра чётная. Поскольку связь между городами не направленная, рассматриваем цифры пары в таком порядке, чтобы чётная цифра оказалась последней. Значит, авиалиния есть между каждой парой городов, в которой хотя бы один город имеет чётный номер; между двумя городами с нечётными номерами авиалинии нет.

На графе вершины с чётными номерами соединены со всеми остальными вершинами, а рёбер между нечётными вершинами нет.

Например, города 1 и 2 соединены: число 12 делится на 2. Города 2 и 9 тоже соединены: можно составить число 92.

По графу есть путь 1 → 2 → 9.

Ответ: да, из города 1 можно добраться в город 9.