Если представляет собой график с максимальной степенью 3 и является минор H , то G является топологическим минор H .
Википедия цитирует этот результат из «Теории графов» Дистеля. В последней версии книги он указан как Опора 1.7.4. В книге нет доказательств или цитирования.
Известно ли местонахождение (оригинальное) доказательство этого?
Кроме того, есть ли ссылка, доказывающая, что если - путь или подразделение когтя и минор H, то G - подграф H ? Это упоминается здесь кратко, но не хватает ссылки.
Ответы:
Поскольку минор H , G можно получить из H , удалив ребра, изолированные вершины и выполнив сжатие ребер. Также легко показать, что мы можем настаивать на том, что сначала выполняются операции с подграфами, т. Е. Мы можем сначала выполнить все удаления ребер и вершин, а затем выполнить все сокращения ребер. Более того, давайте ограничим определение «сжатие ребер», чтобы запретить сжимающиеся ребра, где одна из вершин имеет степень 1. Сокращение такого ребра такое же, как удаление его, поэтому это не изменит определение младших графов.грамм ЧАС грамм ЧАС
Пусть будет графом, полученным из H , выполнив сначала все удаления ребер / вершин. H 'по- прежнему содержит G как минор. Если мы покажем, что HЧАС' ЧАС ЧАС' грамм содержит G как топологическое минорто мы сделали, так как определение топологического несовершеннолетнему также позволяет край / вершинных удалений.ЧАС' грамм
Поскольку можно получить из H ′грамм ЧАС' от края сжатия только, и все промежуточные графики должны иметь максимальную степень 3 , так как не существует никакого способа , чтобы уменьшить максимальную степень графа путем выполнения сжатия кромки. (Это было бы возможно, если бы мы допустили сжатие ребер, падающих на вершину степени 1.)ЧАС'
Итак, рассмотрим любой шаг в преобразованииЧАС' в . Единственные типы ребер, которые мы можем сжать, это те, которые имеют вершины степени 2 или одну вершину степени 2 и одну вершину степени 3. (Все другие комбинации не работают. Например, ребра с двумя вершинами степени-3 приведут к вершине степени 4 при сокращении.)грамм
И теперь мы закончили, так как если получается из H 2 путем сжатия ребра с двумя вершинами степени 2, то H 2 может быть получено из H 1 , выполняя разбиение ребра на этом ребре. Аналогично для ребра с одной вершиной степени 3 и одной вершиной степени 2. Таким образом, H ' может быть получено из G только путем выполнения краевых подразделений, что означает, что G является топологическим минором H 'ЧАС1 ЧАС2 ЧАС2 ЧАС1 ЧАС' G G H′ и , следовательно , .H
Мы также нуждались в этом результате для статьи один раз, поэтому мы включили краткое доказательство в нашу статью. Вы можете найти результат в квантовой сложности запросов свойств второстепенных замкнутых графов . Это упомянуто на странице 13. Однако этот факт скрыт в доказательстве чего-то другого и явно не сформулирован как теорема.
Также интересно то, что есть обратное утверждение к этой теореме:
источник