Задачка про количество циклов в планарном графе

[AlexBo]

Здравия желаю,

Люди добрые, как можно коротко и наглядно показать, что если в графе не более трех циклов, то у него нет шансов не быть планарным?

[worm2]

Интересная задача.
Но я бы попросил уточнить. Считаются ли циклы, содержащие одну и ту же вершину более одного раза?
Например, вот граф с пятью вершинами: 1, 2, 3, 4, 5 и шестью рёбрами (1,2), (2,3), (3,1), (1,4), (4,5), (5,1). Сколько в нём циклов? Понятно, что два несомненных цикла это 1-2-3 и 1-4-5, а вот 1-2-3-1-4-5 и 1-2-3-1-5-4 — они тоже считаются циклами? И если да, то эти два длинных цикла между собой разные или считаются одним и тем же? От ответов на эти вопросы зависит, должны ли мы доказывать утверждение для подобных графов тоже, или же можно их не рассматривать, т.к. у них более трёх циклов.

[B@R5uk]

Все рёбра, не входящие в циклы можно выкинуть, так как они в конечном счёте могут быть размещены на плоскости. Все оставшиеся циклы сократить до трёх вершин и трёх рёбер. А потом подумать что может остаться после такого преобразования. Комбинаций будет не много.

[Munin]

Теоремой Куратовского пользоваться можно?

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.