Задание
Связный плоский граф с десятью ребрами разбивает плоскость на несколько областей: одну внешнюю и три внутренних.
Найдите количество вершин графа.
Решение
Правило
Теорема Эйлера для связного плоского графа
Если связный плоский граф имеет \(\displaystyle V\small\) вершин и \(\displaystyle E\small\) ребер и разбивает плоскость на \(\displaystyle F\small\) областей, то
\(\displaystyle V-E+F=2\small.\)
По условию,
\(\displaystyle F=1+3=4\small,\) \(\displaystyle E=10\small.\)
По теореме Эйлера
\(\displaystyle V=E-F+2=10-4+2=8\small.\)
Итак, в графе \(\displaystyle 8\) вершин.
Ответ: \(\displaystyle 8\small.\)