В одной из вершин (а) октаэдра; (b) куба сидит муха. Может ли она проползти по всем его рёбрам ровно по одному разу и возвратиться в исходную вершину?

Ответ: (а) да, может; (b) нет, не может.

Разбираемся:

(a) Октаэдр:

• Октаэдр имеет 6 вершин и 12 ребер.
• Каждая вершина октаэдра соединена с 4 другими вершинами.
• Граф является эйлеровым, если все вершины имеют четную степень (количество ребер, соединенных с вершиной).
• В октаэдре все вершины имеют степень 4 (четная), следовательно, муха может проползти по всем ребрам ровно один раз и вернуться в исходную вершину.

(b) Куб:

• Куб имеет 8 вершин и 12 ребер.
• Каждая вершина куба соединена с 3 другими вершинами.
• В кубе все вершины имеют степень 3 (нечетная), следовательно, муха не может проползти по всем ребрам ровно один раз и вернуться в исходную вершину.

Ответ: (а) да, может; (b) нет, не может.