В одной из вершин а) октаэдра; б) куба сидит муха. Может ли она проползти по всем его рёбрам ровно по одному разу и возвратиться в исходную вершину?
Решение
а) Пусть, A, B, C, A1, B1, C1 – вершины октаэдра, причём (A, A1), (B, B1) и (B, B1) – пары противоположных вершин. Тогда любая пара вершин, кроме этих трёх, соединяется ребром. Путь мухи может быть следующим: ABA1C1BCAC1B1CA1B1A (см. рис.)
б) В каждой из восьми вершин куба сходится по три ребра. Это означает, что степень каждой вершины полученного графа нечётна, значит, путешествие совершить невозможно.