Проверьте, пожалуйста. Допустим критерий
верен.
Будем рассматривать только графы с одной вершиной и некоторым числом
ребер (петель). Назовем такой граф
букетом петель. Тогда из критерия следует неравенство
. Я хочу доказать, если это неравенство выполняется, тогда рассматриваемые графы вкладываются в поверхность.
Пусть
-- произвольный букет
петель. Возможны два случая: (1)
не содержит пересекающиеся петли; (2)
содержит не менее одной пары пересекающихся петель. В случае (1) очевидно, что
вкладывается в сферу. Рассмотрим случай (2). Известно, что в этом случае
(пока без пояснений). Положим
. Тогда
или
. Осталось показать, что если
имеет одну и более пересекающиеся ленточки и
, тогда
вложим в поверхность рода
. Это следует из теоремы, которая утверждает, что
любой букет петель с конечным числом ленточек можно вложить в некоторую замкнутую ориентируемую поверхность путем добавления некоторого числа ручек.
Будет ли справедливо такое доказательство?