142
правки
Изменения
Нет описания правки
Пусть <tex>G</tex> произвольный граф с <tex>V</tex> вершинами (<tex>V \ge 3</tex>), <tex>E</tex> ребрами и <tex>F</tex> гранями. Тогда <tex>E \le 3V - 6</tex>
|proof=
Поскольку <tex>G</tex> не содержит петель и кратных ребер, то каждая грань граничит хотя бы с тремя ребрами. Пусть, двигаясь вдоль <tex>i</tex>-й грани мы пройдем <tex>l_i</tex> ребер. Очевидно, что <tex>\sum_{i=1}^{F}l_i = 2E</tex>. Поскольку <tex>l_i \ge 3 </tex> <tex>\hspace{3pt} (i = 1..F)</tex>, получаем <tex>3F \le 2E</tex>. Из формулы Эйлера <tex>3E - 3V + 6 = 3F \le 2E</tex>, то есть <tex>E \le 3V - 6</tex>.
}}
