Изменения

Покажем, что если теорема верна для графов с <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= 2</tex>

[[Файл:Hypercube.gif|350px|thumb|right|Пример невыпуклого многоугольника для которого <tex dpi = 100>V - E + F = 0</tex>. Многоугольник получен путем вырезания куба внутри куба.]]Для доказательства соотношения Эйлера представим поверхность выпуклого многогранника сделанной из эластичного материала. Удалим (вырежем) одну из его граней и оставшуюся поверхность растянем на плоскости. Получим сеткупланарный граф, содержащую содержащий <tex>F' = F - 1</tex> многоугольников (которые, по-прежнему, будем называть гранями)внутренних граней, <tex>V</tex> вершин и <tex>E</tex> ребер.

Для этой сетки Тогда справедливо уже доказанное соотношение, известное из планиметрии: <tex>V - E + F ' = 1 </tex>.

* Асанов М,, Баранский В., Расин В. {{---}} Дискретная математика {{---}} Графы, матроиды, алгоритмы (стр. 104 - 107)* О.Оре {{---}} Графы и их применение (стр. 131 - 135)