Изменения

Перейти к: навигация, поиск

Теорема Вагнера

17 байт добавлено, 17:05, 18 ноября 2016
Нет описания правки
# Если в G существует минор содержащий <tex> K_{5} </tex>, тогда в G существует подграф гомеоморфный либо <tex> K_{3, 3} </tex> , либо <tex> K_{5} </tex>.
Доказательство первой части
Если в G существует минор содержащий <tex> K_{3, 3} </tex>,значит существуют вершины множества вершин <tex> U_{1} </tex>,<tex> U_{2} </tex>,<tex> U_{3} </tex>,<tex> W_{1} </tex>,<tex> W_{2} </tex>,<tex> W_{3} </tex> попарно не пересекающиеся, образующие индуцированный связанный подграф G, такие что для каждого i и j существует <tex> {u_{i, j} \in U_{i}} </tex> и <tex> {w_{i, j} \in W_{j}} </tex>, такие что (<tex> {u_{i,j}} </tex>,<tex> {w_{i,j}} </tex>) принадлежит множеству ребер исходного графа. Следовательно для каждого i существует поддерево в G с тремя листами как минимум, по одиному лист в каждом <tex> W_{j} </tex>, и с его другими вершинами внутри <tex> U_{i} </tex>. Ситуация с j симметрична.
В следствие леммы о рукопожатиях дерево с тремя вершинами гомеоморфно <tex> K_{1, 3} </tex>. Таким образом, в G существует подграф гомеоморфный шести копиям <tex> K_{1, 3} </tex> соедененные три на три, т.е. получаем <tex> K_{3, 3} </tex>.
Доказательство второй части
Анонимный участник

Навигация