Страница 19 номер 39, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Может ли не быть планарным граф, в котором: а) три вершины; б) четыре вершины?
а) Не может. Пусть вершины графа — \(A\), \(B\), \(C\). Расположим их в вершинах треугольника. Ребро между двумя вершинами проведём по стороне треугольника, а если таких рёбер несколько (кратные рёбра), — дугами рядом с этой стороной, вложенными одна в другую: у таких дуг общие только концы. Петли при вершине проведём маленькими петлями, вложенными одна в другую, возле этой вершины снаружи треугольника. Рёбра, которых в графе нет, не проводим; несвязный граф располагается так же. Рёбра не имеют общих точек, кроме вершин, — граф плоский. Значит, любой граф с тремя вершинами планарный.
б) Не может. Пусть вершины графа — \(A\), \(B\), \(C\), \(D\). Расположим \(A\), \(B\), \(C\) в вершинах треугольника, а \(D\) — внутри него. Тогда все шесть рёбер, которые могут соединять две разные вершины, — стороны \(AB\), \(BC\), \(CA\) и отрезки \(DA\), \(DB\), \(DC\) — не имеют общих точек, кроме вершин: это плоское изображение графа тетраэдра. Рёбра, которых в графе нет, не проводим, кратные рёбра проводим дугами рядом со своим ребром, вложенными одна в другую, петли — маленькими петлями возле своей вершины. Получается плоский граф. Значит, любой граф с четырьмя вершинами планарный.
Ответ: а) нет, любой граф с тремя вершинами планарный; б) нет, любой граф с четырьмя вершинами планарный.
