Хорхе писал(а):
Dementor писал(а):
максимальный планарный граф 4-вершинно-связен.
Неправда, граф икосаэдра 5-связен.
мы рассматриваем только 2- мерный случай.)
Добавлено спустя 4 минуты 38 секунд:Хорхе писал(а):
В планарном графе на

вершинах не более

ребер (это легко следует из формулы Эйлера). Тогда найдется вершина, из которой выходит меньше 6 ребер.
вот я нашел подобное : для плоского графа
то есть, при большем числе ребер граф заведомо непланарен. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.
в итоге мы взрываем всех соседей этой вершины и нефть нельзя перекачать в эту вершину . получается ,что решение найдено!!!