После распада империи, состоявшей из 16 княжеств, выяснилось, что каждое княжество дружит с тремя другими княжествами и враждует со всеми остальными. Можно ли разбить эти княжества на 8 пар дружественных княжеств? Другими словами, нарисуйте граф, из каждой из 16 вершин которого выходит по 3 ребра, в котором нельзя найти 8 рёбер без общих вершин (то есть вершины нельзя разбить на 8 пар соседних вершин). В книге «Тысяча и одна задача по математике» эта задача есть под номером 638. Это видео из альбома • Графы для начинающих
