6. В Тридевятом царстве лишь один вид транспорта — ковёр-самолёт. Из столицы выходит 21 ковровая дорожка, в город Дальний — одна, а из всех остальных городов — по 20. Можно ли из столицы долететь в Дальний (возможно, с пересадками)?

Да. Рассмотрим города и дорожки как вершины и рёбра графа. Степень столицы равна 21, степень города Дальний — 1; обе степени нечётные. Степени всех остальных городов равны 20 и чётны.

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

Ответ: да, из столицы можно добраться в Дальний.