Страница 22 номер 46, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Докажите, что для плоского связного графа выполняется неравенство \(e \le 3v - 6\), где \(v\) — число вершин, а \(e\) — число рёбер.
Неравенство верно не для любого плоского связного графа: у графа из двух вершин и одного ребра \(e = 1\), а \(3v - 6 = 0\). Докажем его для простого графа, у которого не меньше трёх вершин.
Пусть граф конечный, связный, плоский и простой, то есть без петель и кратных рёбер, и в нём \(v \geqslant 3\) вершин; \(f\) — число его областей.
Степень каждой области не меньше 3. Действительно, область степени 1 ограничена петлёй. Граница области степени 2 — либо две петли, либо два кратных ребра, либо одно ребро, которое при обходе проходится дважды; в последнем случае к концам этого ребра не примыкают другие рёбра, то есть весь граф — одно ребро с двумя вершинами. В нашем графе нет петель и кратных рёбер, а вершин не меньше трёх, поэтому областей степени 1 и 2 в нём нет.
Суммарная степень областей равна удвоенному числу рёбер, то есть \(2e\), а каждая из \(f\) областей имеет степень не меньше 3, поэтому \(2e \geqslant 3f\). По формуле Эйлера \(v - e + f = 2\), откуда \(f = 2 - v + e\): \[\begin{aligned} 2e &\geqslant 3(2 - v + e); \\ 2e &\geqslant 6 - 3v + 3e; \\ 3v - 6 &\geqslant e. \end{aligned}\]
Значит, \(e \leqslant 3v - 6\).
Ответ: у простого связного плоского графа, у которого не меньше трёх вершин, \(e \leqslant 3v - 6\).
Докажите, что для плоского связного графа выполняется неравенство \(e \le 3v - 6\), где \(v\) — число вершин, а \(e\) — число рёбер.
Неравенство верно не для любого плоского связного графа: у графа из двух вершин и одного ребра \(e = 1\), а \(3v - 6 = 0\). Докажем его для простого графа, у которого не меньше трёх вершин.
Пусть граф конечный, связный, плоский и простой, то есть без петель и кратных рёбер, и в нём \(v \geqslant 3\) вершин; \(f\) — число его областей.
Степень каждой области не меньше 3. Действительно, область степени 1 ограничена петлёй. Граница области степени 2 — либо две петли, либо два кратных ребра, либо одно ребро, которое при обходе проходится дважды; в последнем случае к концам этого ребра не примыкают другие рёбра, то есть весь граф — одно ребро с двумя вершинами. В нашем графе нет петель и кратных рёбер, а вершин не меньше трёх, поэтому областей степени 1 и 2 в нём нет.
Суммарная степень областей равна удвоенному числу рёбер, то есть \(2e\), а каждая из \(f\) областей имеет степень не меньше 3, поэтому \(2e \geqslant 3f\). По формуле Эйлера \(v - e + f = 2\), откуда \(f = 2 - v + e\). Подставим это выражение в неравенство: \[\begin{aligned} 2e &\geqslant 3(2 - v + e); \\ 2e &\geqslant 6 - 3v + 3e; \\ 3v - 6 &\geqslant e. \end{aligned}\]
Значит, \(e \leqslant 3v - 6\).
Ответ: у простого связного плоского графа, у которого не меньше трёх вершин, \(e \leqslant 3v - 6\).
