74. Приведите пример связного плоского графа с четырьмя вершинами, который разбивает плоскость: а) на 3 области; б) на 4 области.

Для связного плоского графа число областей равно E − V + 2, где E — число рёбер, V — число вершин.

а) Возьмём граф K₄ без одного ребра: четыре вершины и пять рёбер. Он плоский и связный, поэтому число областей равно 5 − 4 + 2 = 3.

б) Возьмём полный граф K₄, который можно нарисовать плоско как треугольник с четвёртой вершиной внутри, соединённой со всеми вершинами треугольника. В нём шесть рёбер, поэтому число областей равно 6 − 4 + 2 = 4.

Ответ: а) K₄ без одного ребра; б) K₄.