17A. Плоские графы

Вовочка вырезал из волейбольной сетки кусок (см. рисунок) и, когда на него начали ругаться, заявил, что это материал для занятий теорией графов: узлы сетки --- это вершины, а соединяющие их верёвочки --- рёбра. Чтобы продемонстрировать свои знания, Вовочка заявил, что в этом графе рёбер на 45 больше, чем вершин. Не ошибается ли Вовочка?

Справа нарисован план квартиры мечты Наталии Павловны. Она состоит из квадратных комнат, между каждыми двумя соседними из которых есть запертая дверь. Какое наименьшее число дверей нужно открыть, чтобы кот, отдыхающий в одной из комнат, мог гулять по всей квартире?

Ниже изображены правильные многогранники. Но, с другой стороны, это графы. а) Нарисуйте эти графы на плоскости так, чтобы их рёбра не пересекались. б) Посчитайте для каждого из них число вершин, рёбер и граней и вычислите В-Р$+$Г.

а) В связном графе В$= 10$, из каждой вершины выходит 3 ребра. Найдите Р. б) В плоском графе все 10 граней --- треугольники. Найдите Р.

Шесть человек встали в круг. Оказалось, что каждый знаком с обоими своими соседями, а также с человеком, стоящим напротив него. Является граф знакомств этой компании планарным?

У Наталии Павловны есть игра <<Туми иши>> из 16 многогранников. Как вы думаете: а) для каждого ли из них соответствующий граф вершин и рёбер является планарным? б) чего у каждого из этих многогранников больше: рёбер, вершин или граней?

Справа нарисованы дачные участки, разделённые 18 заборами. На каждом заборе между двумя участками сидит мальчишка. Рассмотрим два графа:\\ Граф (1): вершины --- это столбы (выделенные жирными точками), рёбра --- соединяющие их заборы.\\ Граф (2): вершины --- участки, а ребром соединены соседние участки. а) Изобразите второй граф. Является ли он планарным? б) Как связаны между собой вершины, рёбра и грани двух этих графов и как связаны их количества?

Нарисуйте двойственные графы для а) всех деревьев с четырьмя вершинами; б) цикла с пятью вершинами; в) любых двух правильных многогранников.

Футбольный мяч сшит из 32 лоскутков: белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый --- с тремя чёрными и тремя белыми. Сколько лоскутков белого цвета?