Решение задачи 74

Рассмотрим к5 - полный граф на 5 вершинах(граф, у которого каждая вершина связана с каждой). Легко нарисовать такой граф в 3-D пространстве. Вершины графа являются вершинами двух тетраэдров, у которых совпадает одна грань. Ребра графа - ребра этих тетраэдров и отрезок, который соединяет две оставшихся вершины. Выглядит это римерно так:

Давайте теперь покажем, что полный граф на пяти вершинах нельзя нарисовать на плоскости без пересечения рёбер.

Заметим, что если уже нарисован полный граф на четырёх вершинах, то всегда можно выбрать треугольник такой, что четвертая вершина попадет внутрь этого треугольника. Вот пример полного графа на 4 вершинах (красным выделен треугольник, внутрь которого попадает зеленая вершина:

Этот граф разбивает плоскость на 4 области. Заметим, что куда бы мы не поставили пятую вершину x, найдется еще одна вершина, которую нельзя соединить с x, не пересекая ранее нарисованные ребра.

Таким образом, нельзя на плоскости нарисовать граф к5 без пересечения ребер, а в пространстве это сделать довольно просто.