Question

Существует ли планарный 4-регулярный граф на 6 вершинах?
(k-регулярный граф - граф, у которого степень каждой из вершин равна k)

Answer 1

Ответ: Существует.

Пример смотрите на картинке:

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