P.S. Воспользуемся теоремой Куратовского об условии планарности графов. Предположим, что данный граф не планарен. Тогда там есть подграф K(3, 3), так как для K(5) степень вершины слишком маленькая. Рассмотрим дополнение к графу. Это будут три ребра. По принципу Дирихле, концы хотя бы одного попадут в разные компоненты подграфа K(3, 3), а тогда в исходном графе такого ребра нет, значит, нет и подграфа K(3, 3). Тогда граф планарен.
ответ: Существует.
Пример смотрите на картинке:
P.S. Воспользуемся теоремой Куратовского об условии планарности графов. Предположим, что данный граф не планарен. Тогда там есть подграф K(3, 3), так как для K(5) степень вершины слишком маленькая. Рассмотрим дополнение к графу. Это будут три ребра. По принципу Дирихле, концы хотя бы одного попадут в разные компоненты подграфа K(3, 3), а тогда в исходном графе такого ребра нет, значит, нет и подграфа K(3, 3). Тогда граф планарен.