Question

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

Answer 1

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

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

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

Answer 2

Нет, не существует планарного 4-регулярного графа на 6 вершинах.

По формуле Эйлера для планарных графов, которая гласит: V - E + F = 2, где V - количество вершин, E - количество ребер, F - количество граней, можно заметить, что для 6 вершин в планарном графе количество граней не может быть равным 2. Это означает, что не существует планарного графа на 6 вершинах, у которого каждая вершина имеет степень 4.