Решение задачи 328

Условие:

(Формула Эйлера) Пусть связный плоский граф с V вершинами и E ребрами разрезает плоскость на F связных кусков (граней). Тогда V−E+F=2.

Решение:

Будем доказывать по индукцию по числу граней.

База индукции
Пусть грань одна, тогда граф представляет из себя дерево. Обозначим количество вершин и ребер в дереве через V и E соответственно. Для всякого дерева верно соотношение: V=E+1. Нетрудно видеть, что в этом случае формула Эйлера выполняется: V−E+F = V−E+1 = 1+1 = 2. База доказана.

Переход

Пусть для любого графа с F гранями формула Эйлера верна. Нарисуем произвольный граф с F+1 гранью (назовем этот граф исходным). Так как F+1 ≥1, то в этом графе есть цикл. Рассмотрим произвольное ребро в этом цикле, оно разделяет две разные грани. Удалим это ребро, тогда две эти грани станут одной гранью. По предположению индукции для нового графа формула Эйлера верна. Пусть у него V вершин и E ребер, тогда V−E+F=2. У исходного графа F+1 грань, V вершин и E+1 ребро. Проверим формулу Эйлера для исходного графа: V−(E+1)+(F+1) = V−E+F=2. Переход доказан.