15
правок
Изменения
Нет описания правки
<br/><tex>V - E + F = 2</tex>
|proof=
[[Файл:Многоугольник.GIF|150px|thumb|right|рис. 1]]
[[Файл:плоский граф.gif|150px|thumb|right|рис. 2]]
Воспользуемся методом математической индукции по количеству граней графа.
<br />
'''База индукции''': <br />
<tex>F = 2</tex>. Граф <tex>G</tex> представляет собой многоугольник с <tex>n</tex> вершинами (рис. 1). Тогда <tex>V = E = n</tex>, значит, равенство <tex>V - E + F = 2</tex> выполняется.
<br />
'''Индукционный переход''':
<br />
Покажем, что если теорема верна для графов с <tex>F</tex> гранями, то она будет верна и для графов с <tex>F + 1</tex> гранями. Пусть <tex>G</tex> - плоский граф, имеющий <tex>V</tex> вершин, <tex>E</tex> ребер и <tex>F</tex> граней, и для него справедлива формула Эйлера. Добавим новую грань (пунктирная линия на рис.2), проводя по внешней грани <tex>F_{\infty}</tex> некоторую элементарную цепь, соединяющую две вершины максимального цикла графа <tex>G</tex>. Если эта цепь имеет <tex>r</tex> ребер, то необходимо добавить <tex>r - 1</tex> новых вершин и одну новую грань. Ясно, что формула Эйлера останется справедливой и для нового графа, так как <tex>V' - E' + F' = (V + r - 1) - (E + r) + (F + 1) = V - E + F</tex>
}}
{{Теорема
