ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 106: *. Эйлерова характеристика

Нам дано количество областей (граней) F=5. Указаны степени этих областей: 3,3,3,3,5.

В теории графов степень области равна количеству рёбер на её границе. Если мы просуммируем степени всех областей, то каждое ребро будет учтено ровно дважды (так как каждое ребро разделяет две области или является границей одной области с двух сторон в случае мостов/петель, но в простых плоских графах без петель и кратных рёбер это стандартное свойство). Однако нужно быть внимательным: если граф не является двусвязным, могут быть нюансы, но базовое соотношение 1/2sumoffacedegrees=E верно для связных плоских графов, где каждое ребро принадлежит двум граням (внешняя грань тоже считается).

Вычислим сумму степеней областей:

Так как сумма степеней областей должна быть чётной (равна 2E), а число 17 — нечётное, возникает противоречие уже на этом этапе для любого графа, где каждое ребро граничит с двумя различными областями (или одной областью дважды, что также добавляет 2 к сумме).

Даже если предположить, что я ошибся в интерпретации «степени области» (например, речь шла о степенях вершин, но условие говорит именно об областях), давайте проверим возможность существования такого графа через формулу Эйлера.

Формула Эйлера для связного плоского графа:

Из шага 1 мы знаем, что 2E=сумма степеней областей. В условии сказано, что области имеют степени 3,3,3,3,5. Сумма равна 17. Это означает, что 2E=17, откуда E=8.5. Количество рёбер в графе должно быть целым числом. Следовательно, такой граф не может существовать.

Примечание: Иногда под «степенями областей» могут подразумевать степени вершин, ограничивающих область, но даже в этом случае сумма длин циклов (границ областей) должна быть четной, так как каждое ребро входит в границу ровно двух областей (если граф двусвязен) или учитывается дважды при обходе. Для любого конечного графа сумма степеней всех вершин равна 2E (чётное число). Аналогично, сумма степеней всех граней (длин их границ) равна 2E (для связного плоского графа без мостов, влияющих на подсчет иначе, но в общем случае длина границы каждой грани складывается из рёбер, и каждое ребро участвует в формировании границ двух граней, либо одной грани дважды, что всё равно дает вклад 2 в сумму длин).

Поскольку сумма заданных степеней областей (17) является нечётным числом, она не может быть равна 2E для целого числа рёбер E.

Так как сумма степеней всех областей плоского графа должна быть равна удвоенному числу рёбер (2E), то есть должна быть чётным числом, а в условии сумма равна 17 (нечётное число), то такой граф не существует.