Задача
Пусть связный плоский граф с V вершинами и E рёбрами разрезает плоскость на F кусков. Докажите формулу Эйлера: V – E + F = 2.
Решение
Будем удалять рёбра по одному, пока граф не превратится в дерево (как в задаче 131098 а). На каждом шаге число как число рёбер, так и число кусков уменьшается на 1 (при удалении ребра два примыкающих к нему куска сливаются в один). Поэтому величина V – E + F не меняется. Но для полученного дерева она равна 2, поскольку E = V – 1 (см. задачу 131098 б), а F = 1.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет